Return Index of Maximum with Equal Possibility - Facebook

https://gist.github.com/gcrfelix/21c5eca538bec217f837
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=123655&highlight=facebook
randomly return the index of max element in array
给一个全是数字的数组，随机返回0到当前位置中最大值得坐标
比如【1,2,3,3,3,3,1,2】
在最后一个2的时候有4个3都是最大值，要按1/4的概率返回其中一个3的index

最简单的解法当然是跑一遍array，把max elements的index记录到list中，然后random一下list，即可满足题意。

这样是O(N) time, O(N) space

follow up: 如果要求O（1）space呢？（或者说如果是个infinite array呢）

这时候不能记录 index 了，只能在遍历数组时，记录一个当前遇到的最大值：max，以及最大值的个数：counter
同时维持一个 ret 变量，每次遇到 max 时，以 1/count 的概率更新 ret 为当前位置。
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
这样最后能保证 ret 是随机的一个max的index么，可以的，比如：

【1,2,3,3,3,3,1,2】
. visit 1point3acres.com for more.
可以用递推证明，比如遇到第k个max时，假设它被返回的概率是随机的，即1/k，那么第k + 1个max出现的时候，按我们的替换方式，有 k/k+1的可能k ＋ 1不会被选中，也就是第k个max 幸存的概率为 被选中的概率*不被k+1换走的概率 = 1/k * k/(k + 1) = 1/(k + 1)
public int findMax(int[] array) {
  int len = array.length;
  int result = -1;
  int max = Integer.MIN_VALUE;
  int count = 0;
  for(int i=0; i<len; i++) {
    if(array[i] == max) {
      count ++;
      int num = new Random.nextInt(count);
      if(num == 0) {
        result = i;
      }
    } else if(max == Integer.MIN_VALUE || array[i] > max) {
      max = array[i];
      result = i;
      count = 1;
    }
  }
  return result;