一题算法|求随机数索引
程序员文章站
2022-03-14 22:52:51
...
题目描述
给定一个可能含有重复元素的整数数组,要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意:
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
题目示例
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);
// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);
这题目中有一个地方需要注意,每一个索引返回的概率都是相同的。比较笨的方法就是将与 target 相等的元素存放到一个中间集合中,最后从中间集合随机取一个。第二种办法就是利用蓄水池抽样法来解决这个问题。
解法一:使用中间集合
我们先从头到尾遍历数组,将与 target 相等元素的索引,集中存储到中间集合 list 中,最后再从中间集合中随机返回一个元素索引。
1、解题代码:
class Solution {
private int[] nums;
public Solution(int[] nums) {
this.nums = nums;
}
public int pick(int target) {
// 开辟一个中间集合
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
// 找出与target相等的元素
if (nums[i] == target) {
list.add(i);
}
}
// 如果只存在一个,就直接返回
if (list.size() == 1) return list.get(0);
// 如果有两个以上,随机取一个
return getRandomIndex(list);
}
/**
* 随机给出下标
*
* @param list 给定元素的索引集合
* @return
*/
public int getRandomIndex(List<Integer> list) {
return list.get(new Random().nextInt(list.size()));
}
}
复杂度分析
时间复杂度:需要遍历一次数组,所以时间复杂度是O(N)
空间复杂度:使用了 ArrayList ,ArrayList 的大小与数组有关,所以空间复杂度为O(N)
解法二:蓄水池抽样算法
这是我在 leetcode 上看到的解法,蓄水池抽样算法好像是一种专业的算法,关于算法的详情,大家就自行百度,我也不是太清楚,这里我就简单的描述:给定一个数据流,数据流长度N很大,且N直到处理完所有数据之前都不可知,请问如何在只遍历一遍数据(O(N))的情况下,能够随机选取出m个不重复的数据。符合我们的题意,这里我就直接给出解题代码,具体的也不是很清楚,不过刷题不就是扩宽思维吗?
1、解题代码
class Solution {
private int[] nums;
public Solution(int[] nums) {
this.nums = nums;
}
public int pick(int target) {
// 返回下标,没找到就返回-1
int index = -1;
// 记录查找到的个数
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
count++;
// 随机返回,new Random().nextInt() % count == 0 作为概率
if (new Random().nextInt() % count == 0) index = i;
}
}
return index;
}
}
复杂度分析
时间复杂度:需要遍历一次数组,所以时间复杂度是O(N)
空间复杂度:没有使用新的集合,所以空间复杂度为O(1)
最后
欢迎扫码关注微信公众号:「平头哥的技术博文」,和平头哥一起学习,一起进步。