Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/528.html


Algorithm

This question gives an array of weights.

Let us randomly pick points based on the weights. The current points are not randomly selected with equal probability, but should be selected based on different weights. For example, in example 2, the weight is [1, 3], which means that there are two points, the weights are 1 and 3 respectively, then the probability of one point is one-fourth, and the probability of the other one is four-quarters. three.

Since our rand() function is random with equal probability, then how can we weight random, we can use a trick, since the weights are 1 and 3, the sum is 4, then we now assume that there are 4 points, Then randomly pick a point with equal probability.

After random to the first point, it represents the original first point, and random to the last three points represents the original second point, so that the weight is random. Then we can create the cumulative sum array of the weight array.

For example, if the weight array is [1, 3, 2], then the cumulative sum array is [1, 4, 6], and the entire weight sum is 6, we rand() % 6, you can randomly get a number in the range [0, 5], random to 0 is the first point, random to 1, 2, 3 is the second point, random to 4, 5 is the third Point, so we randomly find a number x, and then add and find the first number greater than the random number x in the array, and use the binary search method to find the coordinates of the first number greater than the random number x, which is what you want

Code

  • public class Random_Pick_with_Weight {
    
        // i hate these stats random questions
        class Solution {
            private int[] presum;
            private int n;
            private Random rand;
    
            public Solution(int[] w) {
                n = w.length;
                presum = new int[n];
                rand = new Random();
                presum[0] = w[0];
                for (int i = 1; i < n; i++) presum[i] = presum[i - 1] + w[i];
            }
    
            public int pickIndex() {
                int r = rand.nextInt(presum[n - 1]) + 1;
                int i = Arrays.binarySearch(presum, r);
                if (i < 0) i = -(i + 1);
                return i;
            }
        }
    
    }
    
    
    ############
    
    class Solution {
        private int[] s;
        private Random random = new Random();
    
        public Solution(int[] w) {
            int n = w.length;
            s = new int[n + 1];
            for (int i = 0; i < n; ++i) {
                s[i + 1] = s[i] + w[i];
            }
        }
    
        public int pickIndex() {
            int x = 1 + random.nextInt(s[s.length - 1]);
            int left = 1, right = s.length - 1;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (s[mid] >= x) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left - 1;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(w);
     * int param_1 = obj.pickIndex();
     */
    
  • // OJ: https://leetcode.com/problems/random-pick-with-weight/
    // Time: O(W) for both APIs
    // Space: O(W)
    class Solution {
    private:
        int sum;
        vector<int> w;
    public:
        Solution(vector<int> w): w(w) {
            srand (time(NULL));
            sum = accumulate(w.begin(), w.end(), 0);
        }
        
        int pickIndex() {
            int r = rand() % sum;
            for (int i = 0; i < w.size(); ++i) {
                r -= w[i];
                if (r < 0) return i;
            }
        }
    };
    
  • class Solution:
        def __init__(self, w: List[int]):
            self.s = [0]
            for c in w:
                self.s.append(self.s[-1] + c)
    
        def pickIndex(self) -> int:
            x = random.randint(1, self.s[-1])
            left, right = 1, len(self.s) - 1
            while left < right:
                mid = (left + right) >> 1
                if self.s[mid] >= x:
                    right = mid
                else:
                    left = mid + 1
            return left - 1
    
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(w)
    # param_1 = obj.pickIndex()
    
    ############
    
    class Solution:
    
        def __init__(self, w):
            """
            :type w: List[int]
            """
            self.preSum = [0] * len(w)
            self.preSum[0] = w[0]
            for i in range(1, len(w)):
                self.preSum[i] = self.preSum[i - 1] + w[i]
    
        def pickIndex(self):
            """
            :rtype: int
            """
            total = self.preSum[-1]
            rand = random.randint(0, total - 1)
            left, right = 0, len(self.preSum) - 1
            while left + 1 < right:
                mid = (left + right) // 2
                if rand >= self.preSum[mid]:
                    left = mid
                else:
                    right = mid
            if rand < self.preSum[left]:
                return left
            return right
    
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(w)
    # param_1 = obj.pickIndex()
    
  • type Solution struct {
    	s []int
    }
    
    func Constructor(w []int) Solution {
    	n := len(w)
    	s := make([]int, n+1)
    	for i := 0; i < n; i++ {
    		s[i+1] = s[i] + w[i]
    	}
    	return Solution{s}
    }
    
    func (this *Solution) PickIndex() int {
    	n := len(this.s)
    	x := 1 + rand.Intn(this.s[n-1])
    	left, right := 1, n-1
    	for left < right {
    		mid := (left + right) >> 1
    		if this.s[mid] >= x {
    			right = mid
    		} else {
    			left = mid + 1
    		}
    	}
    	return left - 1
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * obj := Constructor(w);
     * param_1 := obj.PickIndex();
     */
    
  • /**
     * @param {number[]} w
     */
    var Solution = function (w) {
        const n = w.length;
        this.s = new Array(n + 1).fill(0);
        for (let i = 0; i < n; ++i) {
            this.s[i + 1] = this.s[i] + w[i];
        }
    };
    
    /**
     * @return {number}
     */
    Solution.prototype.pickIndex = function () {
        const n = this.s.length;
        const x = 1 + Math.floor(Math.random() * this.s[n - 1]);
        let left = 1,
            right = n - 1;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (this.s[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    };
    
    /**
     * Your Solution object will be instantiated and called as such:
     * var obj = new Solution(w)
     * var param_1 = obj.pickIndex()
     */
    
    
  • use rand::{thread_rng, Rng};
    
    struct Solution {
        sum: Vec<i32>,
    }
    
    /**
     * `&self` means the method takes an immutable reference.
     * If you need a mutable reference, change it to `&mut self` instead.
     */
    impl Solution {
        fn new(w: Vec<i32>) -> Self {
            let n = w.len();
            let mut sum = vec![0; n + 1];
            for i in 1..=n {
                sum[i] = sum[i - 1] + w[i - 1];
            }
            Self { sum }
        }
    
        fn pick_index(&self) -> i32 {
            let x = thread_rng().gen_range(1, self.sum.last().unwrap() + 1);
            let (mut left, mut right) = (1, self.sum.len() - 1);
            while left < right {
                let mid = (left + right) >> 1;
                if self.sum[mid] < x {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            (left - 1) as i32
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * let obj = Solution::new(w);
     * let ret_1: i32 = obj.pick_index();
     */
    
    
  • class Solution {
        int[] accumulatedWeights;
        int totalWeight;
    
        public Solution(int[] w) {
            int length = w.length;
            accumulatedWeights = new int[length];
            accumulatedWeights[0] = w[0];
            for (int i = 1; i < length; i++)
                accumulatedWeights[i] = accumulatedWeights[i - 1] + w[i];
            totalWeight = accumulatedWeights[length - 1];
        }
        
        public int pickIndex() {
            int random = (int) (Math.random() * totalWeight);
            int index = binarySearch(random);
            return index;
        }
    
        private int binarySearch(int target) {
            int low = 0, high = accumulatedWeights.length;
            while (low < high) {
                int mid = (high - low) / 2 + low;
                int curWeight = accumulatedWeights[mid];
                if (curWeight == target)
                    return mid + 1;
                else if (curWeight > target)
                    high = mid;
                else
                    low = mid + 1;
            }
            return low;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(w);
     * int param_1 = obj.pickIndex();
     */
    ############
    
    class Solution {
        private int[] s;
        private Random random = new Random();
    
        public Solution(int[] w) {
            int n = w.length;
            s = new int[n + 1];
            for (int i = 0; i < n; ++i) {
                s[i + 1] = s[i] + w[i];
            }
        }
    
        public int pickIndex() {
            int x = 1 + random.nextInt(s[s.length - 1]);
            int left = 1, right = s.length - 1;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (s[mid] >= x) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left - 1;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(w);
     * int param_1 = obj.pickIndex();
     */
    
  • // OJ: https://leetcode.com/problems/random-pick-with-weight/
    // Time: O(W) for both APIs
    // Space: O(W)
    class Solution {
    private:
        int sum;
        vector<int> w;
    public:
        Solution(vector<int> w): w(w) {
            srand (time(NULL));
            sum = accumulate(w.begin(), w.end(), 0);
        }
        
        int pickIndex() {
            int r = rand() % sum;
            for (int i = 0; i < w.size(); ++i) {
                r -= w[i];
                if (r < 0) return i;
            }
        }
    };
    
  • class Solution:
        def __init__(self, w: List[int]):
            self.s = [0]
            for c in w:
                self.s.append(self.s[-1] + c)
    
        def pickIndex(self) -> int:
            x = random.randint(1, self.s[-1])
            left, right = 1, len(self.s) - 1
            while left < right:
                mid = (left + right) >> 1
                if self.s[mid] >= x:
                    right = mid
                else:
                    left = mid + 1
            return left - 1
    
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(w)
    # param_1 = obj.pickIndex()
    
    ############
    
    class Solution:
    
        def __init__(self, w):
            """
            :type w: List[int]
            """
            self.preSum = [0] * len(w)
            self.preSum[0] = w[0]
            for i in range(1, len(w)):
                self.preSum[i] = self.preSum[i - 1] + w[i]
    
        def pickIndex(self):
            """
            :rtype: int
            """
            total = self.preSum[-1]
            rand = random.randint(0, total - 1)
            left, right = 0, len(self.preSum) - 1
            while left + 1 < right:
                mid = (left + right) // 2
                if rand >= self.preSum[mid]:
                    left = mid
                else:
                    right = mid
            if rand < self.preSum[left]:
                return left
            return right
    
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(w)
    # param_1 = obj.pickIndex()
    
  • type Solution struct {
    	s []int
    }
    
    func Constructor(w []int) Solution {
    	n := len(w)
    	s := make([]int, n+1)
    	for i := 0; i < n; i++ {
    		s[i+1] = s[i] + w[i]
    	}
    	return Solution{s}
    }
    
    func (this *Solution) PickIndex() int {
    	n := len(this.s)
    	x := 1 + rand.Intn(this.s[n-1])
    	left, right := 1, n-1
    	for left < right {
    		mid := (left + right) >> 1
    		if this.s[mid] >= x {
    			right = mid
    		} else {
    			left = mid + 1
    		}
    	}
    	return left - 1
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * obj := Constructor(w);
     * param_1 := obj.PickIndex();
     */
    
  • /**
     * @param {number[]} w
     */
    var Solution = function (w) {
        const n = w.length;
        this.s = new Array(n + 1).fill(0);
        for (let i = 0; i < n; ++i) {
            this.s[i + 1] = this.s[i] + w[i];
        }
    };
    
    /**
     * @return {number}
     */
    Solution.prototype.pickIndex = function () {
        const n = this.s.length;
        const x = 1 + Math.floor(Math.random() * this.s[n - 1]);
        let left = 1,
            right = n - 1;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (this.s[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    };
    
    /**
     * Your Solution object will be instantiated and called as such:
     * var obj = new Solution(w)
     * var param_1 = obj.pickIndex()
     */
    
    
  • use rand::{thread_rng, Rng};
    
    struct Solution {
        sum: Vec<i32>,
    }
    
    /**
     * `&self` means the method takes an immutable reference.
     * If you need a mutable reference, change it to `&mut self` instead.
     */
    impl Solution {
        fn new(w: Vec<i32>) -> Self {
            let n = w.len();
            let mut sum = vec![0; n + 1];
            for i in 1..=n {
                sum[i] = sum[i - 1] + w[i - 1];
            }
            Self { sum }
        }
    
        fn pick_index(&self) -> i32 {
            let x = thread_rng().gen_range(1, self.sum.last().unwrap() + 1);
            let (mut left, mut right) = (1, self.sum.len() - 1);
            while left < right {
                let mid = (left + right) >> 1;
                if self.sum[mid] < x {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            (left - 1) as i32
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * let obj = Solution::new(w);
     * let ret_1: i32 = obj.pick_index();
     */
    
    

All Problems

All Solutions