528. Random Pick with Weight

leetcode medium

#array#backtracking#csharp#leetcode#medium#prefix-sum#search

Task

Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i.

Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w).

Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%).

Пример:

Input

["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]

[[[1,3]],[],[],[],[],[]]

Output

[null,1,1,1,1,0]

Explanation

Solution solution = new Solution([1, 3]);

solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.

solution.pickIndex(); // return 1

solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.

All of the following outputs can be considered correct:

[null,1,1,1,1,0]

[null,1,1,1,1,1]

[null,1,1,1,0,0]

[null,1,1,1,0,1]

[null,1,0,1,0,0]

......

and so on.

C# solution

matched/original

public class Solution {
    private int[] prefixSums;
    private int totalSum;
    public Solution(int[] w) {
        prefixSums = new int[w.Length];
        int prefixSum = 0;
        for (int i = 0; i < w.Length; i++) {
            prefixSum += w[i];
            prefixSums[i] = prefixSum;
        }
        totalSum = prefixSum;
    }
    public int PickIndex() {
        double target = totalSum * new Random().NextDouble();
        for (int i = 0; i < prefixSums.Length; i++) {
            if (target < prefixSums[i]) {
                return i;
            }
        }
        return prefixSums.Length - 1;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private vector<int>& prefixSums;
    private int totalSum;
    public Solution(vector<int>& w) {
        prefixSums = new int[w.size()];
        int prefixSum = 0;
        for (int i = 0; i < w.size(); i++) {
            prefixSum += w[i];
            prefixSums[i] = prefixSum;
        }
        totalSum = prefixSum;
    }
    public int PickIndex() {
        double target = totalSum * new Random().NextDouble();
        for (int i = 0; i < prefixSums.size(); i++) {
            if (target < prefixSums[i]) {
                return i;
            }
        }
        return prefixSums.size() - 1;
    }
}

Java solution

matched/original

class Solution {
    private int[] prefixSums;
    private int totalSum;

    public Solution(int[] w) {
        this.prefixSums = new int[w.length];

        int prefixSum = 0;
        for (int i = 0; i < w.length; ++i) {
            prefixSum += w[i];
            this.prefixSums[i] = prefixSum;
        }
        this.totalSum = prefixSum;
    }

    public int pickIndex() {
        double target = this.totalSum * Math.random();
        int i = 0;
        for (; i < this.prefixSums.length; ++i) {
            if (target < this.prefixSums[i])
                return i;
        }
        return i - 1;
  }
}

JavaScript solution

matched/original

class Solution {
    constructor(w) {
        this.prefixSums = new Array(w.length).fill(0);
        let prefixSum = 0;
        for (let i = 0; i < w.length; i++) {
            prefixSum += w[i];
            this.prefixSums[i] = prefixSum;
        }
        this.totalSum = prefixSum;
    }

    pickIndex() {
        const target = this.totalSum * Math.random();
        for (let i = 0; i < this.prefixSums.length; i++) {
            if (target < this.prefixSums[i]) {
                return i;
            }
        }
        return this.prefixSums.length - 1;
    }
}

Python solution

matched/original

import random

class Solution:
    def __init__(self, w: List[int]):
        self.prefixSums = []
        prefixSum = 0
        for weight in w:
            prefixSum += weight
            self.prefixSums.append(prefixSum)
        self.totalSum = prefixSum

    def pickIndex(self) -> int:
        target = self.totalSum * random.random()
        for i, prefixSum in enumerate(self.prefixSums):
            if target < prefixSum:
                return i
        return len(self.prefixSums) - 1

Go solution

matched/original

import (
    "math/rand"
    "time"
)

type Solution struct {
    prefixSums []int
    totalSum   int
}

func Constructor(w []int) Solution {
    prefixSums := make([]int, len(w))
    prefixSum := 0
    for i, weight := range w {
        prefixSum += weight
        prefixSums[i] = prefixSum
    }
    return Solution{prefixSums, prefixSum}
}

func (this *Solution) PickIndex() int {
    rand.Seed(time.Now().UnixNano())
    target := float64(this.totalSum) * rand.Float64()
    for i, prefixSum := range this.prefixSums {
        if target < float64(prefixSum) {
            return i
        }
    }
    return len(this.prefixSums) - 1
}

Explanation

Algorithm

Инициализация и предобработка весов:

В конструкторе создайте массив накопительных сумм prefixSums, где каждая позиция будет содержать сумму всех предыдущих весов до текущего индекса включительно.

Также в конструкторе сохраните общую сумму весов totalSum.

Генерация случайного числа и выбор индекса:

В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum.

Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу.

Возврат результата:

Верните найденный индекс.

😎