הכנס את מחק GetRandom


רמת קושי בינוני
נשאל לעתים קרובות לאשר אמזון בעברית AppDynamics תפוח עץ בלומברג מצודה פייסבוק Google מיקרוסופט Nvidia אורקל קוארה טויטר שתי סיגמא Yandex Zillow
מערך עיצוב בליל

ב Insert Insert GetRandom בעיה עלינו לעצב מבנה נתונים התומך בכל הפעולות הבאות ב מְמוּצָע זמן O (1).

  1. insert (val): מכניס פריט val לערכה אם הוא עדיין לא קיים.
  2. remove (val): מסיר שווי פריט מהסט אם קיים.
  3. getRandom: מחזיר אלמנט אקראי מתוך קבוצת האלמנטים הנוכחית. כל אלמנט חייב להכיל את אותה הסתברות של להיות מוחזר.

מכיוון שהשאלה זקוקה להפעלה ומחיקה ב- O (1), ולכן אנו זקוקים למפה. אך לשיטת getRandom (), אנו זקוקים למבנה נתונים מבוסס אינדקס כמו מערך, כך שנוכל לבחור באופן אקראי כל אלמנט אינדקס שיחזיר.

לפיכך, כדי לקבל את כל שלוש הפונקציות, נוכל להשתמש הן במפה והן במערך יחד. בואו נראה איך

נקודות חשובות

  1. הכנסה ב מערך הוא O (1) אם נעשה בחלק האחורי.
  2. המחיקה במערך היא O (1) אם האלמנט מוסר מאחור.

שימוש במבני נתונים

מפה M (לאחסון ערך, זוג אינדקסים)

וקטור V לאחסון הנוכחי של האלמנטים

אלגוריתם להכנסה

  1. בדוק אם האלמנט הנתון קיים במפה:
    • אם קיים, החזר כוזב
    • אַחֵר:
      • הכנס את האלמנט הנתון בסוף וקטור V.
      • הכנס אלמנט נתון וזה אינדקס למפה M
      • תחזיר נכון

אלגוריתם למחיקה

  1. בדוק אם האלמנט הנתון קיים במפה:
    • אם קיים, אז:
      • החלף את הערך הנתון ואת האלמנט האחרון בווקטור (ניתן למצוא את האינדקס באמצעות מפה M)
      • עדכן את המפה כ- M [last_element] = M [given_element]
      • מחק את האלמנט האחרון של הווקטור.
      • מחק את המרכיב הנתון מהמפה
      • תחזיר נכון.
    • אחרת, תחזיר שקר.

אלגוריתם עבור getRandom

  1. בחר כל אינדקס אקראי i
  2. n הטווח של 0 לגודל הווקטור.
  3. אלמנט החזרה הקיים באינדקס זה בווקטור V.

יישום עבור הכנס מחק GetRandom

תוכנית C ++ להכנסת מחק GetRandom

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

class RandomizedSet {
public:
    vector<int> v;
    map<int,int> m;
    RandomizedSet() {
    }
    
    //function for insertion of given value
    bool insert(int val) {
        if(m.find(val)==m.end()){
            v.push_back(val);
            m.insert({val,v.size()-1});
            return true;
        }
        
        return false;
    }
    
    //function for removal of given value
    bool remove(int val) {
        if(m.find(val)!=m.end()){
            int last = v.back();
            m[last]=m[val];
            v[m[val]]=last;
            v.pop_back();
            m.erase(val);
            return true;
        }
        return false;
    }
    
    //function to get a random element 
    int getRandom() {
        int ran = rand()%v.size();
        return v[ran];
    }
};

int main()
{
    RandomizedSet* r = new RandomizedSet();
    r->insert(4);
    r->insert(5);
    cout<<r->getRandom()<<" ";
    r->remove(5);
    cout<<r->getRandom()<<" ";
    return 0;
}
5 4

תוכנית JAVA להכנסת מחק GetRandom

import java.util.*;
public class Main
{
    public static class RandomizedSet {
    
        HashMap<Integer, Integer> m;
        List<Integer> v;
        
        //constructor
        public RandomizedSet() {
            m = new HashMap<>();
            v = new ArrayList<>();
        }
        
        //function for insertion of given value
        public boolean insert(int val) {
            if(m.containsKey(val)) 
                return false;
            v.add(val);
            m.put(val,v.size()-1);
            return true;
        }
        
        //function for removal of given value
        public boolean remove(int val) {
            if(m.containsKey(val)){
                int last = v.get(v.size()-1);
                m.put(last,m.get(val));
                v.set(m.get(val),last);
                v.remove(v.size()-1);
                m.remove(val);
                return true;
            }
            return false;
        }
        
        //function to get a random element 
        public int getRandom() {
            int ran = (int)(Math.random()%v.size());
            return v.get(ran);
        }
    }
  public static void main(String[] args) {
      RandomizedSet obj = new RandomizedSet();
        obj.insert(6);
        obj.insert(5);
        obj.insert(3);
        System.out.print(obj.getRandom()+" ");
        obj.remove(5);
        System.out.print(obj.getRandom()+" ");
        System.out.print(obj.getRandom()+" ");
  }
}
6 6 6

הפניות