Algorithm/function O(1) 中数组中的 returns 随机数并创建单个排列
Algorithm/function that returns random number in array in O(1) and creates single permutation
简介：这是一道面试题，我一直答不出来。代码解决方案会很好（使用任何语言），但 algorithm/pseudocode 也很棒。
问题：这道题是设计一个算法来解决以下问题：
给定一个函数 int getRand(int x)，它随机地获取一个 int x 和 return 一个 int，范围从 0 到 x（仅 - > [0, k)）。对 getRand() 的每次调用都在 O(1) 时间内执行。
您还获得了一个数组 int[] arr，大小为 k，包含整数。
编写一个函数 getRandUnique()，当被调用时将 return 来自 arr 的 随机 成员，这样在 k 请求之后确切地说，您将拥有 arr 成员的完整排列（这实际上意味着 getRandUnique() 将 return 不同的 成员 arr 每次调用）。
每次调用 getRandUnique() 必须在 O(1) 时间内执行。
您可以 use/store 全局变量等...
例如：假设 arr = [2, 3, 5 , 1]。调用 getRandUnique() 将 return 2, 3, 5, 1 的概率为 1/4。对 getRandUnique() 的后续调用将 return 剩余 3 成员中的 1/3 概率等等...
尝试： 我实际上 （经过反复试验）并发布了解决方案 "Q&A Style"。我很想得到一些其他可能的 ideas/solutions。我会接受任何作为正确答案的解决方案（我不想接受我自己的）！
问题：如何在上述所有限制条件下实现？
编辑：现在我知道这个问题对应于 Fisher–Yates shuffle，尽管这里的规范有点 different/more 严格。
我的解决方法如下：
定义index = 0.
调用并赋值index = getRand(k)（记住k是arr的大小）。
将 arr[index] 替换为 arr[k]。
- 现在调用并分配
index = getRand(k-1)。现在您可以确定您不会再次获得索引 k，因此您不必删除它。
- 将
arr[index] 替换为 arr[k-1]
- 继续这样做，直到调用最后一个
getRand(1)。
现在您有一个数组 arr，它是根据要求对自身进行随机排列（甚至不需要额外的数组）。
简介：这是一道面试题，我一直答不出来。代码解决方案会很好（使用任何语言），但 algorithm/pseudocode 也很棒。
问题：这道题是设计一个算法来解决以下问题：
给定一个函数 int getRand(int x)，它随机地获取一个 int x 和 return 一个 int，范围从 0 到 x（仅 - > [0, k)）。对 getRand() 的每次调用都在 O(1) 时间内执行。
您还获得了一个数组 int[] arr，大小为 k，包含整数。
编写一个函数 getRandUnique()，当被调用时将 return 来自 arr 的 随机 成员，这样在 k 请求之后确切地说，您将拥有 arr 成员的完整排列（这实际上意味着 getRandUnique() 将 return 不同的 成员 arr 每次调用）。
每次调用 getRandUnique() 必须在 O(1) 时间内执行。
您可以 use/store 全局变量等...
例如：假设 arr = [2, 3, 5 , 1]。调用 getRandUnique() 将 return 2, 3, 5, 1 的概率为 1/4。对 getRandUnique() 的后续调用将 return 剩余 3 成员中的 1/3 概率等等...
尝试： 我实际上
问题：如何在上述所有限制条件下实现？
编辑：现在我知道这个问题对应于 Fisher–Yates shuffle，尽管这里的规范有点 different/more 严格。
我的解决方法如下：
定义
index = 0.调用并赋值
index = getRand(k)（记住k是arr的大小）。将
arr[index]替换为arr[k]。- 现在调用并分配
index = getRand(k-1)。现在您可以确定您不会再次获得索引k，因此您不必删除它。 - 将
arr[index]替换为arr[k-1] - 继续这样做，直到调用最后一个
getRand(1)。
现在您有一个数组 arr，它是根据要求对自身进行随机排列（甚至不需要额外的数组）。