[LeetCode]Random Pick Index

不让我们用太多空间，我们用时间换空间即可。O(N)时间用Reservoir Sampling生成随机数，常数空间，代码如下：

	class Solution {
	public:
	Solution(vector<int> nums) {
	m_nums = nums;
	}
	int pick(int target) {
	int count = 0, cand = -1;
	for(int i = 0; i < m_nums.size(); ++i)
	{
	if(m_nums[i] == target)
	{
	if(!count)cand = i;
	else
	{
	int random = rand() % (count + 1);
	if(!random)cand = i;
	}
	++count;
	}
	}
	return cand;
	}
	private:
	vector<int> m_nums;
	};
	/**
	* Your Solution object will be instantiated and called as such:
	* Solution obj = new Solution(nums);
	* int param_1 = obj.pick(target);
	*/

view raw Random Pick Index.cpp hosted with ❤ by GitHub