leetcode 398 随机数索引 蓄水池取样算法

缘起

继续研究蓄水池取样算法 leetcode 398 随机数索引

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

注意：
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例:

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);

此题怎么和蓄水池取样问题联系到一起呢? 数组的长度非常大~ 假设你要pick(x), 则我们可以理解为数组中=x的元素的个数是未知的. 而且题干只强调了——不允许使用额外的空间, 并没有提及时间效率. emmm~

对于固定的x, 我们遍历数组, 当有一个x出现的时候，我们就要开始施展蓄水池抽样算法的第一次选择对象——其实就是百分之百选择这个. 再继续遍历, 出现第二个n的时候, 我们施展第二次选择对象. 此次就是以1/2概率选择, 然后等待第三次x的出现, 就是以1/3的概率选择第三个对象. 思想完全借鉴于【1】（【1】是裸的蓄水池取样）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
typedef vector<int>::iterator vit;
public:
	Solution(vector<int>& nums) 
	{
		srand((int)(time(0))); // 和【1】一样, 切记, 时间种子初始化一次即可, 不要放到pick中去, 否则多次调用pick的输出的是一样的
		this->nums = nums;
	}

	int pick(int target) 
	{
		a.clear();
		int cnt = 0, ans, index = 0;
		for (vit x = nums.begin(); x!=nums.end(); x++)
		{
			if (*x==target)
			{
				a.push_back(index); // a中存target出现的索引
				ans = a[rand()%((cnt++)+1)];
			}
			++index;
		}
		return ans;
	}

private:
	vector<int> a, nums;
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
104 ms
, 在所有 cpp 提交中击败了
67.82%
的用户
内存消耗 :
18.8 MB
, 在所有 cpp 提交中击败了
86.67%
的用户

参考

【1】https://yfsyfs.github.io/2019/10/16/leetcode-382-%E9%93%BE%E8%A1%A8%E9%9A%8F%E6%9C%BA%E8%8A%82%E7%82%B9-%E8%93%84%E6%B0%B4%E6%B1%A0%E5%8F%96%E6%A0%B7%E7%AE%97%E6%B3%95/