栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

常数时间删除/查找数组中的任意元素 LeetCode710 LeetCode380

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

常数时间删除/查找数组中的任意元素 LeetCode710 LeetCode380

常数时间删除/查找数组中的任意元素
思路:使用底层用数组实现的,插入时在尾部插入,删除时将待删除元素交换到数组的尾部,再pop
  1. LeetCode380 O(1)时间插入、删除和获取随机元素

    1. 思路分析

      1. 本题难点有两点
        1. 插入、删除、随机获取元素这三个操作的时间复杂度都必须为O(1)
        2. getRandom方法必须等概率返回元素
      2. 解决策略
        1. 针对O(1):
          1. 底层用数组实现,且数组必须是紧凑的,这样用随机数生成索引,getRandom等概率返回元素
          2. 插入和删除:如何使用数组插入、删除时间复杂度为O(1),即将要删除的元素替换为数组最后一个元素,并将数组最后一个元素删除,因此需要一个HashMap记录索引
    2. 代码实现

    3. class RandomizedSet {
          private List list;
          private HashMap valToIndex;
          private Random random;
          public RandomizedSet() {
              list = new ArrayList<>();
              valToIndex = new HashMap<>();
              random = new Random();
          }
      
          public boolean insert(int val) {
              if (valToIndex.containsKey(val)) {
                  return false;
              }
              int index = list.size();
              list.add(val);
              valToIndex.put(val, index);
              return true;
          }
      
          public boolean remove(int val) {
              if (!valToIndex.containsKey(val)) {
                  return false;
              }
              //获取待删除元素的索引
              int delIndex = valToIndex.get(val);
              //获取最后一个元素的值
              int lastVal = list.get(list.size() - 1);
              //将待删除元素替换为最后一个元素
              list.set(delIndex, lastVal);
              //在数组中删除最后一个元素
              list.remove(list.size() - 1);
              //更新valToIndex中,注意是key是val,value是Index
              valToIndex.put(lastVal, delIndex);
              valToIndex.remove(val);
              return true;
          }
      
          public int getRandom() {
              return list.get((int)(random.nextInt(list.size())));
          }
      }
      
      
      
  2. LeetCode710 黑名单中的随机数

    1. 思路分析

      1. 题目分析

        要求我们在[0, n-1]中排除掉黑名单数组后等概率返回剩余某一个数

        例如:输入N = 5, blacklist = [1, 3],多次调用pick函数,会等概率随机返回0,2,4中的某一个数

        且题目要求使用最少的random

      2. 解题思路

        1. 与上一题类似,我们可以将区间[0, N]看作一个数组,然后将blacklist中的元素移到数组中的最末尾last = N -1,同时用一个哈希表进行映射,相当于把黑名单中的数和size之后不是黑名单的数替换

          细节

          1. 如果last在黑名单中,则直接跳过
          2. 如果b >= size, 即b在[size, N - 1]数组中,就没有必要建立映射
          3. 将黑名单中的索引映射到合法数字
        2. 排除黑名单数组后的数组个数size = N - blacklist.size(); 则黑名单中的数字都交换到了[sz, N - 1]区间,[0, sz - 1]中的黑名单数字映射到了正常数字

        3. HashMap中的key是黑名单元素,value是正常元素索引,如图所示

        4. 关于pick函数,随机生成[0, size)之间的整数n,如果n是黑名单元素如1,则返回4;如n不是黑名单元素则返回n,例如0 和 2

    2. 代码实现

      class Solution {
          private int size;
          private HashMap map;
          public Solution(int n, int[] blacklist) {
              size = n - blacklist.length;
              map = new HashMap<>();
              int last = n - 1;
              //将blacklist放入到map,以便查找
              for(int b : blacklist) {
                  map.put(b, -1);
              }
              for(int b : blacklist) {
                  //b在[size, N - 1]数组中,没有必要建立映射
                  if (b >= size) {
                      continue;
                  }
                  //last在黑名单中,直接跳过
                  while (map.containsKey(last)) {
                      last--;
                  }
                  map.put(b, last);
                  last--;
              }
          }
      
          public int pick() {
              int index = (int)(Math.random() * size);
              //若index在黑名单中,则返回map.get(index);否则返回index
              return map.getOrDefault(index, index);
          }
      }
      
      
      
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/946690.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号