Given a list of ints, write "getRandom" function


  • 0
    B

    given a list of integers as such: [5,2,3,1] write getRandom() function where:
    total = 1+2+3+5 = 11
    1 is given with 1 / 11 chance
    2 is given with 2 / 11 chance
    3 is given with 3 / 11 chance
    5 is given with 5 / 11 chance

    Can you do this in constant space?


  • 2
    T

    How about this ?

        public class RandomeClass {
            private int[] dp;
            private int sum;
            private Random random = new Random();
            private int[] nums;
            public RandomeClass(int[] nums) {
                this.nums = nums;
                int len = nums.Length;
                dp = new int[len];
                for (int i = 0; i < len; i++) {
                    sum += nums[i];
                    dp[i] = sum;
                }
            }
    
            public int GetRandom() {
                int low = 0;
                int high = dp.Length;
                int val = random.Next(sum);
    
                while (low < high-1)
                {
                    int mid = low + (high - low) / 2;
                    if (dp[mid] <= val)
                    {
                        low = mid;
                    }
                    else
                    {
                        high = mid;
                    }
                }
    
                if (dp[low] > val)
                {
                    return nums[low];
                }
                else if (dp[high] > val) {
                    return nums[high];
                }
                else
                {
                    return nums[high+1];
                }
            }
        }
    

  • 0
    A

    That's also the best solution I could come up with (O(n) for initialization and O(log n) for picking a number).

    Note that you are not using constant space here, but you could just reuse the nums array instead of creating a new one to get there.

    @bsm can there be duplicates in the list ?


  • 0
    T

    How about this ?

    int GetRandom(int[] arr){
    int sum = arr[0];
    int len = arr.Length;
    var rand = new Random();
    int result = arr[0];
    for(int i = 1;i<len;i++){
        sum+=arr[i];
        if(rand.NextInt(sum) < arr[i]){
           result = arr[i];
        }
    }
      return result;
    }
    

Log in to reply
 

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