[LeetCode] Random Pick Index 随机拾取序列
2023-09-11 14:21:37 时间
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);
这道题指明了我们不能用太多的空间,那么省空间的随机方法只有水塘抽样Reservoir Sampling了,LeetCode之前有过两道需要用这种方法的题目Shuffle an Array和Linked List Random Node。那么如果了解了水塘抽样,这道题就不算一道难题了,我们定义两个变量,计数器cnt和返回结果res,我们遍历整个数组,如果数组的值不等于target,直接跳过;如果等于target,计数器加1,然后我们在[0,cnt)范围内随机生成一个数字,如果这个数字是0,我们将res赋值为i即可,参见代码如下:
class Solution { public: Solution(vector<int> nums): v(nums) {} int pick(int target) { int cnt = 0, res = -1; for (int i = 0; i < v.size(); ++i) { if (v[i] != target) continue; ++cnt; if (rand() % cnt == 0) res = i; } return res; } private: vector<int> v; };
类似题目:
参考资料:
https://discuss.leetcode.com/topic/58371/c-o-n-solution/2
https://discuss.leetcode.com/topic/58297/share-c-o-n-time-solution/2
https://discuss.leetcode.com/topic/58403/bruce-force-java-with-o-n-time-o-1-space
相关文章
- Java实现 LeetCode 835 图像重叠(暴力)
- Java实现 LeetCode 825 适龄的朋友(暴力)
- Java实现 LeetCode 738 单调递增的数字(暴力)
- Java实现 LeetCode 674 最长连续递增序列(暴力)
- Java实现 LeetCode 669 修剪二叉搜索树(遍历树)
- Java实现 LeetCode 657 机器人能否返回原点(暴力大法)
- Java实现 LeetCode 594 最长和谐子序列(滑动窗口)
- Java实现 LeetCode 594 最长和谐子序列(滑动窗口)
- Java实现 LeetCode 1162 地图分析(可以暴力或者动态规划的BFS)
- Java实现 LeetCode 522 最长特殊序列 II(查找最长的非子序列的长度)
- Java实现 LeetCode 5355 T 秒后青蛙的位置
- Java实现 LeetCode 300 最长上升子序列
- Java实现 LeetCode 232 用栈实现队列
- Java实现 LeetCode 148 排序链表
- Java实现 LeetCode 105 从前序与中序遍历序列构造二叉树
- (LeetCode 169) Majority Element
- 每日一道 LeetCode (36):相交链表
- [LeetCode] Excel Sheet Column Number
- LeetCode-1139. 最大的以 1 为边界的正方形【前缀和,矩阵】
- LeetCode-828. 统计子串中的唯一字符【哈希表,字符串,动态规划】
- leetcode 105. 从前序与中序遍历序列构造二叉树
- 【LeetCode 76】最小覆盖子串
- 【LeetCode Python实现】300. 最长递增子序列(中等)动态规划
- Leetcode 1218. 最长定差子序列(提供一种思路)
- Leetcode 594. 最长和谐子序列(已解决)
- Leetcode 1332. 删除回文子序列(看完题解才恍然大悟!!!!!!!)
- 【LeetCode】105. 从前序与中序遍历序列构造二叉树