LeetCode Random Pick Index Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Note: The array size can be very large. Solution that uses too much extra space will not pass the judge. Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);
// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

---

题意：一个数组中有好多数，有些数会有重复，现给定一个target，要从数组中出现target的下标中随机选一个下标出来。 常规解法是，把每个数出现的下标存到一个index二维数组中，至于哪个数存到index的哪个桶里，用一个字典来记录数字和存储位置的关系。然后来一个target时，找到出现target的下标的数组，从数组中随机选一个下标出来。这种思路的代码如下： [cpp] class Solution { private: unordered_map<int, int> dict; vector<vector<int>> index; public: Solution(vector<int> nums) { int pos = 1; for (int i = 0; i < nums.size(); ++i) { if (dict[nums[i]] == 0)dict[nums[i]] = pos++; } index.resize(dict.size() + 1); for (int i = 0; i < nums.size(); ++i) { index[dict[nums[i]]].push_back(i); } } int pick(int target) { int n = index[dict[target]].size(); return index[dict[target]][rand() % n]; } }; [/cpp] 本代码提交之后MLE，内存超了，但是好像所有测试样例都通过了。 看了一下tag，发现需要用到水塘抽样，正好刷过的LeetCode Linked List Random Node用到了这种采样方法。思路马上来了：每次来了一个target，遍历原数组，每遇到一个target，则用水塘采样的方法采样一次下标，最终的效果就相当于从所有出现target的下标中随机采样。这种思路真是妙呀，代码如下： [cpp] class Solution { private: vector<int> mNums; public: Solution(vector<int> nums) { mNums = nums; } int pick(int target) { int n = 0; int ans = 0; for (int i = 0; i < mNums.size(); i++) { if (mNums[i] == target) { ++n; int r = rand() % n; if (r == 0)ans = i; } } return ans; } }; [/cpp] 本代码提交AC，用时99MS。不过我觉得，如果要多次调用pick函数的话，多一点空间，使用第一种解法应该会快很多，因为第一种解法只需要初始化的时候构建hash和index二维数组，后续的pick都是常数时间，而第二种解法每次都需要遍历数组，效率不高。]]>