求问一个算法问题

[winnerczwx]

有一组三维坐标数据 [{x, y, z}, {x, y, z}, ...], 现在需要随机生成一个坐标 且不能和已有坐标重复

x y z 最大值 = 100

请教有什么算法可以实现这个需求吗?

[momocraft]

如果坐标是整数: 把原来的坐标整成带排序的数据结构，然后在“空洞”里随机生成就不会重复

[ianEros]

我想到的也是提前把未使用的坐标存起来，然后在这个集合里面随机，如果最大值 100 ，size 最大值也就 1 ，000 ，000

[zxCoder]

随机就是一种算法，随机算法

[shyrock]

感觉跟 hash 的思路有点像。
OP 能说一下问题的真实背景吗？

[xuanzizhe]

想到的最原始的方法就是先把坐标算出来存在数组里，然后取的时候每次从里面删一条，没啥算法可言了，相信应该有更好的方法勒~ https://reurl.cc/gQpdNX

[vace]

整数的话 xyz 直接转固定长度二进制就行了

0b1100100 0b1100100 0b1100100

=> 0b110010011001001100100

也就：0 ～ 1651300 ，随机生成点数字的工作。

[xuanbg]

建立一个 size 为 100 的 3 维空间，就是一个[100,100,100]的 3 维数组并初始化好。然后随机在这个 3 维空间中取一个就行空的点就行了。

[Tanix2]

从已有坐标构建哈希表，随机生成坐标，通过比较哈西判断是否重复，重复则重新随机生成。

[shiji]

评论区真是精彩啊。 不看不知道，一看吓一跳。

[Jakarta]

原始坐标数据转成"到原点距离: [坐标,坐标,....]"的哈希，随机生成的坐标也计算一下到原点的距离，如果距离存在，就进一步比较坐标值。
不知是否可行？

[wxf666]

如果取值范围是 0 ~ 100 ，一个三维坐标可以映射到一个 0 ~ (101^3-1) 的整数，后面就是生成不重复的随机整数就好

如果换成 bitmap 存储，大概只需 16 KB 内存即可？

[9ine]

有点像 https://leetcode.cn/problems/random-pick-with-blacklist/

[msg7086]

@shiji 确实吓了一跳……几乎没人答对的。

[hackpro]

@shiji 说明刷 leetcode 还是必要的😄

[pagxir]

看描述，可选集合是个有限集合。却没有说有限次数，那大概率是无解。如果只是想把数据顺序乱掉，那就直接用洗牌算法将数据打乱就可以了。

[pagxir]

得到打乱数据，也可以采取抽卡牌的方式，就是从中随机抽中一张，然后跟最顶部一张交换，接着扔掉最顶部的一张，持续这么下去，就得到打乱的数据了。

[sillydaddy]

算法：
```
type Point={x:number, y:number, z:number};

let blacklist:Point[] = [....................]; //初始化已有的三维坐标数据

let pickRandomPointThatIsNotInBlackList = ():Point=>{
while(true){
let x=Math.random()*100;
let y=Math.random()*100;
let z=Math.random()*100;
let inBlackList = blacklist.every(v=>!(v.x==x&&v.y==y&&v.z==z));
if(!inBlackList) return {x,y,z};
}
}
```

测试：
console.log( pickRandomPointThatIsNotInBlackList() );

[sillydaddy]

```
let inBlackList = blacklist.every(v=>!(v.x==x&&v.y==y&&v.z==z));
if(!inBlackList) return {x,y,z};
}
```
改为
```
let notInBlackList = blacklist.every(v=>!(v.x==x&&v.y==y&&v.z==z));
if(notInBlackList) return {x,y,z};
}
```

[sillydaddy]

所以算法就是：先随机出一个坐标点，然后判断一下是否在已有的三维坐标数组中，如果在，就再随机出一个坐标点。直到得到符合条件的点。得到不同坐标点的概率是相等的。

[Rootrl]

用 Hashmap 维护已有坐标，用一个连接符把 xyz 字符拼起来做 key ，比如"x-y-z"，value 随便设置个单字符。剩下就是生成了，然后一样拼起来拿去 hashmap 检索判断

[Jakarta]

@msg7086 别光吓一跳啊，说下你认为的正确答案呀，不是“几乎没人答对”吗？

[msg7086]

@Jakarta wxf666 #11 说了。很普通的高进制数转换。如果取值 0-100 就是一个 101 进制的 3 位数。

[Jakarta]

@msg7086 哦哦好的谢谢。不过如果坐标不是整数呢？

[msg7086]

@Jakarta 不是整数的话就基本不需要考虑坐标重复的问题了。
一定要考虑的话可以对整个坐标做 hash ，也就是用 hashmap 来实现。
但是 3 个 double 的空间有 192bit ，你一秒取一个可以取到宇宙毁灭都不一定有重复。