每日算法-力扣380

解法#

python解法#

import random
class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.val2idx = dict() # val: index

    def insert(self, val):
        if val in self.val2idx:
            return False
        self.val2idx[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val):
        if val not in self.val2idx:
            return False
        # O(1)取下标，不再index遍历
        idx = self.val2idx[val]
        last = self.nums[-1]

        # 末尾元素覆盖+更新map
        self.nums[idx] = last
        self.val2idx[last] = idx

        # 删尾部、删key
        self.nums.pop()
        del self.val2idx[val]
        return True

    def getRandom(self):
        return random.choice(self.nums)

Java解法#

public class RandomizedSet {
    private ArrayList<Integer> nums;
    private HashMap<Integer, Integer> valIndexMap;
    private Random random;

    public RandomizedSet() {
        nums = new ArrayList<>();
        valIndexMap = new HashMap<>();
        random = new Random();
    }

    // O(1)插入
    public boolean insert(int val) {
        if (valIndexMap.containsKey(val)) {
            return false;
        }
        // 新元素放在数组末尾
        valIndexMap.put(val, nums.size());
        nums.add(val);
        return true;
    }

    // O(1)删除：目标位置和末尾交换，删除尾部
    public boolean remove(int val) {
        if (!valIndexMap.containsKey(val)) {
            return false;
        }
        // 1.O(1)获取待删下标、最后一个元素
        int delIndex = valIndexMap.get(val);
        int lastVal = nums.get(nums.size() - 1);

        // 2.末尾元素覆盖待删位置
        nums.set(delIndex, lastVal);
        // 3.更新末尾元素的下标映射
        valIndexMap.put(lastVal, delIndex);

        // 4.删除末尾元素 + 删除map中val
        nums.remove(nums.size() - 1);
        valIndexMap.remove(val);
        return true;
    }

    // O(1)随机等概率取元素
    public int getRandom() {
        int randIdx = random.nextInt(nums.size());
        return nums.get(randIdx);
    }
}

Go解法#

package main

import (
	"math/rand"
	"time"
)

type RandomizedSet struct {
	nums  []int
	idxMap map[int]int
}

func Constructor() RandomizedSet {
	rand.Seed(time.Now().UnixNano())
	return RandomizedSet{
		nums:  make([]int, 0),
		idxMap: make(map[int]int),
	}
}

// 插入
func (rs *RandomizedSet) Insert(val int) bool {
	if _, ok := rs.idxMap[val]; ok {
		return false
	}
	rs.idxMap[val] = len(rs.nums)
	rs.nums = append(rs.nums, val)
	return true
}

// 删除
func (rs *RandomizedSet) Remove(val int) bool {
	index, ok := rs.idxMap[val]
	if !ok {
		return false
	}
	lastVal := rs.nums[len(rs.nums)-1]

	// 末尾值覆盖要删除的下标
	rs.nums[index] = lastVal
	// 更新末尾元素的下标映射
	rs.idxMap[lastVal] = index

	// 截断最后一位 O(1)
	rs.nums = rs.nums[:len(rs.nums)-1]
	// map删掉目标key
	delete(rs.idxMap, val)
	return true
}

// 随机等概率取一个
func (rs *RandomizedSet) GetRandom() int {
	return rs.nums[rand.Intn(len(rs.nums))]
}

总结#

三种方法虽然属于不同编程语言，但是原理都是一样的,提供k-v型的数据结构保存下标和值的关系,再用数组存储唯一值 之所以不选择set来存储唯一值，是因为set不方便实现等概率读取。本算法的关键在于,将被删元素与数组末尾元素互换，完成了O(1)的删除操作。 k-v结构，又实现了O(1)的查找工作。