Medium
https://leetcode.com/problems/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.
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);
思路: use random to ensure equal possibility, key point is save extra space.
解法1: for easier understanding, we create arraylist to store all index of target, and count total,
Then we use random from [0,total), to equally pick any element in the array
Complexity: O(N)time O(m)space - # of target in nums
public class Solution { int[] nums; Random rand; public Solution(int[] nums) { this.nums = nums; this.rand = new Random(); } public int pick(int target) { int total = 0;//total index match target int res = -1; List<Integer> list = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { total++; list.add(i); } } res = list.get(rand.nextInt(total)); //int in [0,total) return res; } }
解法2: To use no extra space, we pick the index in place.
(Reservoir Sampling) update by 1/total in the loop
靠前的index一开始选中的几率高,但是后面loop剩的多被replace的几率也高
举例有5个元素:
对于第二个index来说,1/2(pick)*2/3(replace)*3/4(replace)*4/5(replace) = 1/5;
对于最后一个index来说,就是 1/5(pick) = 1/total.
public class Solution { int[] nums; Random rand; public Solution(int[] nums) { this.nums = nums; this.rand = new Random(); } public int pick(int target) { int total = 0;//total index match target int res = -1; for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { total++; int x = rand.nextInt(total);//[0,total) if(x == 0){ res = i; } } } return res; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(nums); * int param_1 = obj.pick(target); */
No comments:
Post a Comment