题目链接

O(1)时间插入、删除和获取随机元素

题目描述

image.png

实现代码

个人实现代码：

  1. class RandomizedSet {
  3.     Map<Integer, Boolean> containMap = new HashMap();
  5.     int size = 0;
  7.     Random rand = new Random();
  9.     public RandomizedSet() {
  11.     }
  13.     public boolean insert(int val) {
  14.         if(getVal(val)) {
  15.             return false;
  16.         }
  17.         containMap.put(val, true);
  18.         size++;
  19.         return true;
  20.     }
  22.     public boolean remove(int val) {
  23.         if(getVal(val)) {
  24.             containMap.remove(val);
  25.             size--;
  26.             return true;
  27.         }
  28.         return false;
  29.     }
  31.     public int getRandom() {
  33.         int index = rand.nextInt(size) + 1;
  34.         int val = 0;
  35.         for(Map.Entry<Integer, Boolean> entry : containMap.entrySet()) {
  36.             val = entry.getKey();
  37.             if(--index == 0) {
  38.                 break;
  39.             }
  40.         }
  41.         return val;
  42.     }
  44.     private Boolean getVal(int key) {
  45.         return containMap.get(key) != null;
  46.     }
  47. }
  49. /**
  50. * Your RandomizedSet object will be instantiated and called as such:
  51. * RandomizedSet obj = new RandomizedSet();
  52. * boolean param_1 = obj.insert(val);
  53. * boolean param_2 = obj.remove(val);
  54. * int param_3 = obj.getRandom();
  55.  */

参考大佬实现思想：

  1. 定义一个map，一个数组nums，和一个整型变量size
  2. map的key为元素的值，value为该元素在nums数组中的存放索引；
  3. 当insert时，通过map判断是否存在，不存在则map、nums中都插入，同时size+1；
  4. 当remove时，通过map判断是否存在，存在则通过map的value找到在数组nums中的位置，将其与size位置即最后一个位置的元素进行交换，size-1；

实现代码：

  1. class RandomizedSet {
  2.     static int[] nums = new int[200010];
  3.     Random random = new Random();
  4.     Map<Integer, Integer> map = new HashMap<>();
  5.     int idx = -1;
  6.     public boolean insert(int val) {
  7.         if (map.containsKey(val)) return false;
  8.         nums[++idx] = val;
  9.         map.put(val, idx);
  10.         return true;
  11.     }
  12.     public boolean remove(int val) {
  13.         if (!map.containsKey(val)) return false;
  14.         int loc = map.remove(val);
  15.         if (loc != idx) map.put(nums[idx], loc);
  16.         nums[loc] = nums[idx--];
  17.         return true;
  18.     }
  19.     public int getRandom() {
  20.         return nums[random.nextInt(idx + 1)];
  21.     }
  22. }

PS：个人参考思想以后写的代码没AC，离谱：

  1. class RandomizedSet {
  3.     Map<Integer, Integer> map = new HashMap();
  5.     int[] nums = new int[100002];
  7.     int size = 0;
  9.     Random rand = new Random();
  11.     public RandomizedSet() {
  13.     }
  15.     public boolean insert(int val) {
  16.         if(map.containsKey(val)) {
  17.             return false;
  18.         }
  19.         map.put(val, size);
  20.         nums[size++] = val;
  21.         return true;
  22.     }
  24.     public boolean remove(int val) {
  25.         Integer location = map.get(val);
  26.         if(location == null) {
  27.             return false;
  28.         }
  29.         map.remove(val);
  30.         nums[location] = nums[--size];
  31.         map.put(nums[location], location);
  32.         return true;
  33.     }
  35.     public int getRandom() {
  36.         return nums[rand.nextInt(size)];
  37.     }
  38. }
  40. /**
  41.  * Your RandomizedSet object will be instantiated and called as such:
  42.  * RandomizedSet obj = new RandomizedSet();
  43.  * boolean param_1 = obj.insert(val);
  44.  * boolean param_2 = obj.remove(val);
  45.  * int param_3 = obj.getRandom();
  46.  */