Təsadüfi Seçim İndeksi LeetCode Həlli

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

Mündəricat

Problem bəyanat

Random Pick Index LeetCode Solution- Bizə “Solution” sinfinin konstruktoru və int tipli “seçmə” funksiyası verilir. kimi “Həll” sinfini həyata keçirməyimiz tələb olunur

Solution(int[] nums) Obyekti massivlə işə salır nums.
int pick(int target) Təsadüfi bir indeks seçir i etibarən nums hara nums[i] == target. Əgər bir neçə etibarlı i varsa, onda hər bir indeksin bərabər qayıtma ehtimalı olmalıdır.

Nümunə və izahat

Input
["Hol", "seç", "seç", "seç"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Buraxılış
[null, 4, 0, 2]

Izahat
Həll həlli = yeni Həll([1, 2, 3, 3, 3]);
həll.seç (3); // O, ya 2, 3 və ya 4 indeksini təsadüfi olaraq qaytarmalıdır. Hər bir indeksin qaytarılma ehtimalı bərabər olmalıdır.
həll.seç (1); // 0 qaytarmalıdır. Massivdə yalnız nums[0] 1-ə bərabər olduğundan.
həll.seç (3); // O, ya 2, 3 və ya 4 indeksini təsadüfi olaraq qaytarmalıdır. Hər bir indeksin qaytarılma ehtimalı bərabər olmalıdır.

Yanaşma

Bu sual sırf icraya əsaslanır. Dəyişməyə icazə vermək üçün bütün funksiyalarda əlçatanlıq Həll sinifində konstruktordan kənar boş massiv və ya 'a' vektorunu təyin edək.

Solution()-da işə salmaq üçün sadəcə olaraq əvvəlcədən təyin edilmiş boş 'a' massivinə ədədlərin dəyərini təyin edin.

İndi pick() funksiyası üçün "a"-dakı bütün dəyərləri təkrarlayın və hədəfin indeksini başqa müvəqqəti boş "temp" massivində saxlayın. "Hədəf" in bütün göstəricilərini eyni dərəcədə ehtimal etmək üçün əsas ehtimal anlayışından istifadə edək. Əvvəlcə tapın massivin ölçüsü 'temp' seçin və 0-dan temp_size-1-ə qədər istənilən dəyəri qaytaran təsadüfi funksiyadan istifadə edin. Təsadüfi funksiya qayıtdığından bərabər olan dəyərlər ehtimal, sual məhdudiyyətimiz üçün kifayətdir.

Kodu

Random Pick Index üçün C++ kodu

class Solution {
    vector<int> a;
public:
    Solution(vector<int>& nums) {
        a=nums;
    }
    
    int pick(int target) {
        vector<int> temp;
        for(int i=0; i<a.size(); i++) {
            if(target == a[i]) {
                temp.push_back(i);
            }
        }
        int n = temp.size();
        int r = rand()%n;
        return temp[r];
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * int param_1 = obj->pick(target);
 */

Random Pick Index üçün Java kodu

class Solution {
    private int[] a;
    private Random rand;
    public Solution(int[] nums) {
        a=nums;
        rand = new Random();
    }
    
    public int pick(int target) {
        List<Integer> indices = new ArrayList<>();
        for(int i=0; i<a.length; i++) {
            if(a[i] == target) {
                indices.add(i);
            }
        }
        int n = indices.size();
        int res = indices.get(rand.nextInt(n));
        return res;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */