RandomPickIndex [source code]

public class RandomPickIndex {
static
/******************************************************************************/
class Solution {
    int[] nums;
    Random rd;

    public Solution(int[] nums) {
        this.nums = nums;
        rd = new Random ();
    }

    public int pick(int target) {
        // init the reservoir
        int i = 0, res = 0;
        while (i < nums.length) {
            if (nums[i] == target) {
                res = i;
                break;
            }
            i++;
        }
        // traverse on
        i++;
        int count = 1;
        while (i < nums.length) {
            if (nums[i] == target) {
                int j = rd.nextInt (++count);
                if (j < 1)
                    res = i;
            }
            i++;
        }
        return i;
    }
}
/******************************************************************************/
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

    public static void main(String[] args) {
        // RandomPickIndex.Solution tester = new RandomPickIndex.Solution();
    }
}

看到这个题目就不想写了, 这个 Reservoir Sampling忘得精光.

算了, 还是专门回去复习了一下; 大概有了点概念;

这题的突破点是这个note, 让你不能用太多的space, 那么这个note所封杀的是什么样的笨办法? 这个思路我觉得就算是你面试的时候也是可能需要表达出来的;

这个笨办法应该很直接, 就是一个count的做法; 就算是用Map而不是用array count, 只要在input里面的数字的type太多, 最后这个Map的size也会很大, 所以这个方法你几乎是可以放弃的;

既然tag给了提示是 Reservoir sampling来做, 应该就是这个算法, 不过暂时还没有想到这里具体应该怎么应用这个算法?

重新总结一下题目要求你做的难点: 比如3, 出现好几个位置, 最后的输出是希望random in all 3's occurrences. 所以笨办法才会要去用counts, 或者说accumulate positions之类的方法;

错办法好过没办法

另外重新提醒一下自己的一个毛病, 我经常希望拿到题目直接就想到一个很聪明很紧致的好办法; 但是有些题目, 这种一帆风顺是不可能的. 这个时候, 往往不要把自己卡死在找这种好办法的僵局里面, 更好的办法, 是从一个笨办法, 甚至是错办法开始, 然后分析为什么这个办法不行? 从这个角度出发来分析, 往往最后能找到关键的优化点和切入口, 想到正确的办法;

更极端一点, 如果对于一个题目, 不仅连错办法都没, 连一点办法都没, 那么对于任何, 你仅仅是感觉可能可以的办法, 也立刻可以开始跑, 然后找出为什么不行, 然后才有可能引导你找到正确的办法; 当然了, 这个过程中往往需要大量的笔算.

重新回到这个题目, 另外一个办法就是, 干脆不count所有的type的number, 而是在每一个pick里面, 只单独找到所有这个参数target的位置, 然后随机? 这个虽然时间上不利, 但是能否满足这个题目的要求? 后来想了一下, 这个算法还是不满足空间有限的要求: 当题目要求告诉你这个array很大的时候, 不仅是告诉你整个array很大, 而是告诉你target的出现位置也肯能很多, 所以单独存target也不行;

那么另外一个简单的做法是这样, 先1pass, 数一下target有多少个, 然后在这个count的范围内生成一个随机的counter, 然后再来一个pass, 每次碰到target就counter--. 这样最后好像也是能找到的; 但是这样的问题也很自然, 就是要走两个pass, WorstCase. 但是这个方法应该是可行的;

最后还是有惊无险的用reservoir做出来了; 不得不说, reservoir这个算法感觉只要掌握了之后还是不难使用的, 最后的速度是291ms (81%), 很不错;

注意我这里的写法, 我这里为什么需要这个count? 因为在这个题目跟之前LinkedList那一题不一样, 这题这里的备选的node是不知道未知的, 所以我要稍微记录一下那些符合target的位置; 但是因为这里的k只有1, 所以最后我们只要有一个count, 然后在这个count内生成一个随机数和k进行比较就行了;

没有editorial;

discussion最优解:

public class Solution {  

    int[] nums;  
    Random rnd;  

    public Solution(int[] nums) {  
        this.nums = nums;  
        this.rnd = new Random();  
    }  

    public int pick(int target) {  
        int result = -1;  
        int count = 0;  
        for (int i = 0; i < nums.length; i++) {  
            if (nums[i] != target)  
                continue;  
            if (rnd.nextInt(++count) == 0)  
                result = i;  
        }  

        return result;  
    }  
}

合成到一步写了, 比我的简练, 不过我觉得只要写出来就是最好的了; 而且我这个写法也更有利于我自己的理解和记忆;

一个讲解:

@lekzeey said in Simple Reservoir Sampling solution:

To those who don't understand why it works. Consider the example in the OJ
{1,2,3,3,3} with target 3, you want to select 2,3,4 with a probability of 1/3 each.

2 : It's probability of selection is 1 (1/2) (2/3) = 1/3
3 : It's probability of selection is (1/2) * (2/3) = 1/3
4 : It's probability of selection is just 1/3

So they are each randomly selected.

这个则是我自己想到了但是懒得写的笨办法:

public int pick(int target) {  
    int count = 0;  
    for(int i = 0; i < a.length; i++) {  
        if(target == a[i]) count++;  
    }  
    int pickIndex = rand.nextInt(count);  
    for(int i = 0; i < a.length; i++) {  
        if(target == a[i]) {  
            if(pickIndex-- == 0) return i;  
        }  
    }  
    return 0; // shouldn't come here  
}

submission最优的基本也都是reservoir. 一点波动而已;

Problem Description

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);

Difficulty:Medium
Total Accepted:30.7K
Total Submissions:69.2K
Contributor:LeetCode
Companies
facebook
Related Topics
reservoir sampling
Similar Questions