fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
常数时间删除/查找数组中的任意元素 :: labuladong的算法小抄
类似LRU的hash配合double linked list也是可行的吧. val作为hash table的key, 返回随机元素就是从hash.keys( ) 里随机返回即可, 不需要遍历double linked list.
@alannesta 不对，和 LRU 半毛钱关系都没有，你说「从 hash.keys( ) 里随机返回」，这个功能怎么实现？不就回到本文讲的这道算法题么？标准的 hash table 根本无法提供「随机返回一个 key」这样的功能，因为 key 的索引是分散在底层 table 上面的，没办法做到 O(1) 时间内随机取一个出来。
像 Python dict 这样提供随机 pop key 的功能，是因为它的 dict 对 hash table 底层实现做了类似本题的改造。
东哥，黑名单的那题。如果从一开始解题，先把思路写出来；然后一步步带着怎么得到思路感觉会好很多。 我的理解是，把数组分为前后两部分，前部分的黑名单数据索引到后半部非黑名单数据。 但是这个理解的得出就要吃力 谢谢
Java Version
/**
* LC380
*/
class RandomizedSet {
List<Integer> list;
HashMap<Integer, Integer> valToIndex;
Random random;
public RandomizedSet() {
list = new ArrayList<>();
valToIndex = new HashMap<>();
random = new Random();
}
public boolean insert(int val) {
if(valToIndex.containsKey(val)){
return false;
}
list.add(val);
valToIndex.put(val, list.size()-1);
return true;
}
public boolean remove(int val) {
if(!valToIndex.containsKey(val)){
return false;
}
int index = valToIndex.get(val);
int last = list.get(list.size() - 1);
list.set(index, last);
list.remove(list.size() - 1);
valToIndex.put(last, index);
valToIndex.remove(val);
return true;
}
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}
/**
* LC710
*/
class Solution {
int size = 0;
HashMap<Integer, Integer> map = new HashMap<>();
public Solution(int n, int[] blacklist) {
size = n - blacklist.length;
for(int item : blacklist){
map.put(item, -1);
}
int last = n - 1;
for(int item : blacklist){
if(item >= size){
continue;
}
while(map.containsKey(last)){
last--;
}
map.put(item, last);
last--;
}
}
public int pick() {
int index = (int)(Math.random()*size);
return map.getOrDefault(index, index);
// if(map.containsKey(index)){
// return map.get(index);
// }
// return index;
}
}
class Solution {
int length;
HashMap<Integer,Integer> map;
Random random;
public Solution(int n, int[] blacklist) {
random = new Random();
//因为黑名单都在n中，所以，随机数在[0,length)中取
length = n - blacklist.length;
map = new HashMap<>();
//标记黑名单
for(int b :blacklist){
map.put(b, -1);
}
int index = length;
//把黑名单中的数和length之后不是黑名单的数替换，用map记录
for(int black : blacklist){
//如果black不在[0,length)区间内 不用替换
if(0 <= black && black < length){
while(index < n){
if(!map.containsKey(index)){
//map记录
map.put(black, index);
index++;
break;
}else{
index++;
}
}
}
}
}
public int pick() {
int i = random.nextInt(length);
if(map.containsKey(i)){
return map.get(i);
}
return i;
}
}
js 版黑名单中的随机数
class Solution {
constructor(N, blacklist) {
this.N = N;
this.blacklist = blacklist;
const mapping = Object.create(null);
// 最终数组中的元素个数
const sz = (this.sz = N - blacklist.length);
// 先将所有黑名单数字加入 map
for (const b of blacklist) {
// 这里赋值多少都可以
// 目的仅仅是把键存进哈希表
// 方便快速判断数字是否在黑名单内
mapping[b] = -1;
}
// 最后一个元素的索引
let last = N - 1;
for (const b of blacklist) {
// 如果 b 已经在区间 [sz, N)
// 可以直接忽略
if (b >= sz) continue;
// 跳过所有黑名单中的数字
while (mapping[last] !== undefined) last--;
// 将黑名单中的索引映射到合法数字
mapping[b] = last;
last--;
}
this.mapping = mapping;
}
pick() {
const { sz, mapping } = this;
// 随机选取一个索引
const index = Math.floor(Math.random() * sz);
// 这个索引命中了黑名单，
// 需要被映射到其他位置
if (mapping[index] !== undefined) {
return mapping[index];
}
// 若没命中黑名单，则直接返回
return index;
}
}
一、实现随机集合 javascript version
var RandomizedSet = function() {
// 存储元素的值
this.nums = new Array();
// 存储每个元素对应在nums中的索引
this.indices = new Map();
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function(val) {
// 若val已存在，不同再插入
if (this.indices.has(val)) {
return false;
}
// 若val不存在，插入到nums尾部
// 并记录val对应的索引值，保存到indices
let index = this.nums.length;
this.nums.push(val);
this.indices.set(val, index);
return true
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function(val) {
// 若val不存在，不用再删除
if (!this.indices.has(val)) {
return false;
}
// 先拿到val的索引
let id = this.indices.get(val);
// 在nums中将最后一个元素覆盖val
this.nums[id] = this.nums[this.nums.length - 1];
// 在indices中更新移动元素的索引值
this.indices.set(this.nums[id], id);
// 出栈nums的尾部重复元素
this.nums.pop();
// 删除indices中val的索引值
this.indices.delete(val);
return true;
};
/**
* @return {number}
*/
RandomizedSet.prototype.getRandom = function() {
// 随机获取nums中的元素
const randomid = Math.floor(Math.random() * this.nums.length);
return this.nums[randomid];
};
二、避开黑名单的随机数 javascript version
var Solution = function(n, blacklist) {
// 正常元素的个数
this.length = n - blacklist.length;
this.mapping = new Map();
// 数组最后一个位置的索引指针
let last = n - 1;
// 将blacklist元素添加到mapping中
for (let b of blacklist) {
this.mapping.set(b, 0);
}
// 修改[0, sz)内的blacklist元素映射索引，映射至[sz, n-1]的正常元素索引
for (let b of blacklist) {
if (b < this.length) {
while (this.mapping.has(last)){
last--;
}
// 将blacjlist中的元素索引映射到last
this.mapping.set(b, last);
last--;
}
}
};
/**
* @return {number}
*/
Solution.prototype.pick = function() {
// 随机生成正常的索引值
var index = Math.floor(Math.random() * this.length);
// 若该索引值是blacklist中的元素，映射到正常元素
if (this.mapping.has(index)) {
return this.mapping.get(index);
}
// 若该索引值是blacklist中的元素，返回正常元素的值
return index;
};
想问问为什么先put再remove与remove后再put结果会不一样 valToIndex.put(last, index); valToIndex.remove(val);
题目一：来一个PHP版本的
class RandomizedSet {
public $values = [];
public $indexs = [];
public function insert($val) {
if(isset($this->indexs[$val])) {
return false;
}
$this->values[] = $val;
$this->indexs[$val] = count($this->values) - 1;
return true;
}
public function remove($val) {
if(!isset($this->indexs[$val])) {
return false;
}
//获取删除元素索引
$idx = $this->indexs[$val];
//获取数组末尾元素，用于和删除元素替换
$lastItem = $this->values[count($this->values)-1];
//末尾元素的索引更新为删除元素索引
$this->indexs[$lastItem] = $idx;
//删除元素索引对应的值修改为末尾元素的值
$this->values[$idx] = $lastItem;
$this->values[count($this->values)-1] = $val;//可以不用赋值，反正后面都要删掉的
//删除末尾元素的值和索引
array_pop($this->values);
unset($this->indexs[$val]);
return true;
}
public function getRandom() {
if(empty($this->values)) {
return false;
}
return $this->values[rand(0,count($this->values) - 1)];
}
}
js版
/**
* @param {number} n
* @param {number[]} blacklist
*/
var Solution = function (n, blacklist) {
//本质上是构造一个映射 这个映射是将黑名单数字映射到白名单去
//使得如果随机到了黑名单里的数字 也可以正常返回有效数字 不需要重复随机数
const blackToWhite = new Map();
// 给黑名单数字打一个标记 任何数字都行 只要到时候可以判断出它是黑名单的就行
for (let i of blacklist) {
blackToWhite.set(i, 66); // 什么数字都行
}
// 白名单的长度 是总长度减去黑名单的长度
let sz = n - blacklist.length;
let last = n - 1; // 从后面找一个可用的白名单数字
// 给黑名单里的数字建立到白名单的映射
for (let item of blacklist) {
// 如果黑名单中的item本来就在区间[sz,n)内 可以直接忽略 不需要映射 因为随机数也不会随机到这个数字
if (item >= sz) { continue; }
// 如果last也在黑名单里面 那么就换一个last 直到找到不在黑名单里的
while (blackToWhite.has(last)) last--;
blackToWhite.set(item, last);
last--;
}
this.blackToWhite = blackToWhite;
this.size = sz;
};
/**
* @return {number}
*/
Solution.prototype.pick = function () {
// 随机选择
const rdm = parseInt(Math.random() * this.size);
if (this.blackToWhite.has(rdm)) {
return this.blackToWhite.get(rdm)
}
return rdm;
};
/**
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(n, blacklist)
* var param_1 = obj.pick()
*/
解题思路
假设黑名单[0,2,4]，区间是[0,4]， n=5
[黑0，白1，黑2，白3，黑4] 转换为 [白3，白1，黑2，黑0，黑4] 且记下map: {"黑0"：白3}映射关系
当在[0,2)中随机查找一个索引，
- 比如index=0,此时查到是黑0，是黑名单元素，那么要找到映射关系下的白3。
- 比如index=1,此时查到是白1，是白名单元素，那么直接输出就可以
代码
// 给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单
// blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
//
// 优化你的算法，使它最小化调用语言 内置 随机函数的次数。
//
// 实现 Solution 类:
//
//
// Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
// int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数
//
//
//
//
// 示例 1：
//
//
// 输入
// ["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
// [[7, [2, 3, 5]], [], [], [], [], [], [], []]
// 输出
// [null, 0, 4, 1, 6, 1, 0, 4]
//
// 解释
// Solution solution = new Solution(7, [2, 3, 5]);
// solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
// // 0、1、4和6的返回概率必须相等(即概率为1/4)。
// solution.pick(); // 返回 4
// solution.pick(); // 返回 1
// solution.pick(); // 返回 6
// solution.pick(); // 返回 1
// solution.pick(); // 返回 0
// solution.pick(); // 返回 4
//
//
//
//
// 提示:
//
//
// 1 <= n <= 10⁹
// 0 <= blacklist.length <- min(10⁵, n - 1)
// 0 <= blacklist[i] < n
// blacklist 中所有值都 不同
// pick 最多被调用 2 * 10⁴ 次
//
//
// Related Topics 哈希表 数学 二分查找 排序 随机化 👍 104 👎 0
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
// leetcode submit region begin(Prohibit modification and deletion)
class Solution {
private int sz;
private Random random;
private HashMap<Integer, Integer> map;
public Solution(int n, int[] blacklist) {
map = new HashMap<Integer, Integer>();
sz = n - blacklist.length;
for (int i : blacklist) {
map.put(i, 666);
}
int last = n - 1;
for (int i : blacklist) {
// 如果i已经在区间[sz,N)
// 直接可以忽略，不需要映射
if (i >= sz) {
continue;
}
// last 位置是白名单
while (map.containsKey(last)) {
// 缩小last
last--;
}
// 把黑名单元素映射到last位置，last的值就是白名单元素值
map.put(i, last);
last--;
}
random = new Random();
}
public int pick() {
// 随机选取一个索引
int index = random.nextInt(sz);
// 如果这个索引命中了黑名单，需要查找映射该位置的白名单值
if(map.containsKey(index)){
return map.get(index);
}
return index;
}
}
/**
* Your Solution object will be instantiated and called as such: Solution obj = new Solution(n,
* blacklist); int param_1 = obj.pick();
*/
// leetcode submit region end(Prohibit modification and deletion)
题目一的Java版本
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
class RandomizedSet {
// 存放元素
List<Integer> nums;
// 记录每个元素在nums中的索引
Map<Integer, Integer> indexes;
Random random;
public RandomizedSet() {
nums = new ArrayList<>();
indexes = new HashMap<>();
random = new Random();
}
public boolean insert(int val) {
// 存在，不插入
if (indexes.containsKey(val)) {
return false;
}
// 获取val的索引
int valIndex = nums.size();
// val为key valIndex为value 存入map中
indexes.put(val, valIndex);
// 记录元素
nums.add(val);
return true;
}
public boolean remove(int val) {
// 不存在，不删除
if (!indexes.containsKey(val)) {
return false;
}
// 拿到当前值的索引
int valIndex = indexes.get(val);
// 拿到当前末尾的数
int lastNum = nums.get(nums.size() - 1);
// 把要删除数val索引valIndex的值，替换为数组的最后一个数lastNum
nums.set(valIndex, lastNum);
// 索引map中，把末位数字的索引值，更新为要删除数字val的索引值
indexes.put(lastNum, valIndex);
// 数组移除末尾元素
nums.remove(nums.size() - 1);
// 索引集合移除要删除的key
indexes.remove(val);
return true;
}
public int getRandom() {
int index = random.nextInt(nums.size());
return nums.get(index);
}
}
不是很明白这个黑名单的时间复杂度，是O(b^2)吗，这个count操作可能太耗时了或者要自己写O1的count，python实现了但是一直在某个大的testcase超时
710 的Java版
class Solution {
private HashMap<Integer, Integer> mapping;
private Random random;
private int size;
public Solution(int n, int[] blacklist) {
mapping = new HashMap();
random = new Random();
size = n - blacklist.length;
for (int black: blacklist) {
mapping.put(black, 666);
}
int last = n - 1;
for (int black: blacklist) {
// if last is already at the end of the range, continue
if (black > size - 1) {
continue;
}
// if last should be blocked, move pointer
while(mapping.containsKey(last)) {
last--;
}
// point black to the end of the range
mapping.put(black, last);
last--;
}
}
public int pick() {
// pick an index within[0, size - 1]
// Note: int nxt = ran.nextInt(10); Returns number between 0-9
int index = random.nextInt(size);
return mapping.containsKey(index) ? mapping.get(index) : index;
}
}
回复：@Yzxsysu
想问问为什么先put再remove与remove后再put结果会不一样 valToIndex.put(last, index); valToIndex.remove(val); 想象一下如果目前只剩下一个元素了，此时你要删除这个，那此时的val也是last，put那一步就会重复添加一个last （如果本来就有那什么都没发生），如果先删，这里立马又给你加上一个，所以此时数组清空了，但是map还留着那最后一个索引。所以只能在后面删除。
不是很明白 为什么第一个不能直接全部用 hashmap, getRandom 也可以 O(1) 拿到一个随机 key 吧？
Python code 成功提交的
class RandomizedSet:
def __init__(self):
self.data = dict()
def insert(self, val: int) -> bool:
if val in self.data:
return False
self.data[val] = val
return True
def remove(self, val: int) -> bool:
if val in self.data:
del self.data[val]
return True
return False
def getRandom(self) -> int:
if len(self.data) > 0:
return random.choice(list(self.data.keys()))
