Given an integer array nums
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.
Implement the Solution class:
Solution(int[] nums)
Initializes the object with the array nums
.int pick(int target)
Picks a random index i
from nums
where nums[i] == target
. If there are multiple valid i's, then each index should have an equal probability of returning.来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/random-pick-index
实现方法比较垃圾,差不多是离散化之后记录下每个数字出现的位置,然后记录有几个位置,然后循环输出(竟然真的会检测概率相等)。
class Solution { public: map<int, int> m; vector<int> t, now; vector<vector<int>> g; Solution(vector<int>& nums) { vector<int> cop = nums; std::sort(nums.begin(), nums.end()); int N = nums.size(), cnt = 0; m.insert(make_pair(nums[0], cnt++)); nums[0] = m[nums[0]], g.push_back(vector<int>()), t.push_back(0), now.push_back(0); for (int i = 1; i < N; i++) { if (nums[i] != nums[i-1]) m.insert(make_pair(nums[i], cnt++)), g.push_back(vector<int>()), t.push_back(0), now.push_back(0); nums[i] = m[nums[i]]; } for (int i = 0; i < N; i++) { g[m[cop[i]]].push_back(i); t[m[cop[i]]]++; } } int pick(int target) { if (m.find(target) == m.end()) return -1; else { int tem = m[target]; now[tem] = (now[tem] + 1) % t[tem]; return g[tem][now[tem]]; } } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(nums); * int param_1 = obj->pick(target); */