Sort+Binary Search. Did not pass the test case though. Can anyone tell me the reason?


  • 0
    T
    public class Solution{
    	Random r;
    	int[] nums;
    	public Solution(int[] nums){
    		Arrays.sort(nums);
    	    this.nums = nums;
    	    r = new Random();
        }
    
    
        public int pick(int target){
    	    int lower = lowerBound(nums,target);
    	    int upper = upperBound(nums,target);
    	    if(nums[upper]==target) upper++;
    	    return r.nextInt(upper-lower)+lower;
        }
    
    
        private int upperBound(int[] nums, int target){
    	    int s = 0, e = nums.length-1;
    	    while(s<e){
    	        int m = s+(e-s)/2;
    	        if(nums[m]>target) e = m;
    	        else s = m+1;
            }
            return s;
        }
    
    
        private int lowerBound(int[] nums, int target){
    	    int s = 0, e = nums.length-1;
    	    while(s<e){
    	        int m = s+(e-s)/2;
    	        if(nums[m]>=target) e = m;
    	        else s = m+1;
            }
            return s;
        }
    }
    

  • 0
    L

    Sorting will change the indexes for all values. This is not what the question is looking for as you would need to stick to the pick a particular index for that the target value and sorting just spoils that.


Log in to reply
 

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