题目链接

思路

• O(1)时间的插入和删除哈希表就可以实现，但是一个哈希表并不能实现随机访问，所以我们可以搭配一个数组，哈希表记录数组中元素的位置信息，这样在随机访问的时候生成随机数，作为数组下标进行索引
• 需要注意在删除的时候，如果要删除的元素不是数组的最后一个元素，那么我们就要把他后面的所有原元素的索引进行修改，这样的话删除操作会变成O(n)，所以我们可以在删除的时候，把待删除的元素和数组最后一个元素互换位置，这样就可以避免这个问题

class RandomizedSet {

    List<Integer> nums = null;
    Map<Integer, Integer> numsLocation = null;
    Random random;

    /**
     * Initialize your data structure here.
     */
    public RandomizedSet() {
        nums = new ArrayList<>();
        numsLocation = new HashMap<>();
        random = new Random();
    }

    /**
     * Inserts a value to the set. Returns true if the set did not already contain the specified element.
     */
    public boolean insert(int val) {

        if (numsLocation.containsKey(val))
            return false;

        numsLocation.put(val, nums.size());
        nums.add(val);

        return true;
    }

    /**
     * Removes a value from the set. Returns true if the set contained the specified element.
     */
        public boolean remove(int val) {
        if (!numsLocation.containsKey(val))
            return false;

        int deleteIndex = numsLocation.get(val), lastVal = nums.get(nums.size() - 1);

        nums.set(deleteIndex, lastVal);
        nums.remove(nums.size() - 1);
        numsLocation.put(lastVal,deleteIndex);
        numsLocation.remove(val);

        return true;
    }

    /**
     * Get a random element from the set.
     */
    public int getRandom() {
        return nums.get(random.nextInt(nums.size()));
    }
}

Go代码

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

/** Initialize your data structure here. */
func Constructor() RandomizedSet {
	return RandomizedSet{
		m:    make(map[int]int),
		nums: []int{},
	}
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.m[val]; ok {
		return false
	} else {
		this.m[val] = len(this.nums)
		this.nums = append(this.nums, val)
		return true
	}
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
	if index, ok := this.m[val]; ok {
		lastIndex := len(this.nums) - 1
		lastVal := this.nums[lastIndex]
		this.nums[index] = lastVal
		this.nums = this.nums[:lastIndex]
		this.m[lastVal] = index
		delete(this.m, val)
		return true
	} else {
		return false
	}
}

/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
	return this.nums[rand.Intn(len(this.nums))]
}