O(n) for java, Any other good idea?


  • 0
    Y
    public class Solution {
        int[]  nums;
        Random mRandom;
    
        public Solution(int[] nums) {
            this.nums = nums;
            mRandom = new Random();
        }
    
        public int pick(int target) {
            int index = 0;
            int cnt = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == target) {
                    cnt++;
                    if (cnt == 1) index = i;
                    else if (mRandom.nextInt(cnt) == 0) index = i;
                }
            }
            return index;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.