ຂຽນ Delete Delete GetRandom  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ຢືນຢັນ Amazon AppDynamics ຈາກຫນາກແອບເປີ Bloomberg Citadel ເຟສບຸກ ກູໂກ Microsoft Nvidia Oracle ຄິວ Twitter ສອງ Sigma Yandex Zillow
Array ການອອກແບບ Hash

ໃນບັນຫາ Delete Delete GetRandom ພວກເຮົາ ຈຳ ເປັນຕ້ອງອອກແບບໂຄງສ້າງຂໍ້ມູນທີ່ສະ ໜັບ ສະ ໜູນ ການ ດຳ ເນີນງານທັງ ໝົດ ຕໍ່ໄປນີ້ ໂດຍສະເລ່ຍ O (1) ເວລາ.

  1. insert (val): ສະແດງກິ່ງງ່າລາຍການໃສ່ຊຸດຖ້າບໍ່ມີຢູ່ແລ້ວ.
  2. remove (val): ເອົາ val item ອອກຈາກຊຸດຖ້າມີ.
  3. getRandom: ສົ່ງຄືນອົງປະກອບແບບສຸ່ມຈາກຊຸດປັດຈຸບັນ. ແຕ່ລະອົງປະກອບຕ້ອງມີ ຄວາມເປັນໄປໄດ້ຄືກັນ ຂອງການຖືກສົ່ງກັບຄືນ.

ໃນຖານະເປັນ ຄຳ ຖາມທີ່ຕ້ອງການການປະຕິບັດງານແລະການລຶບລ້າງໃນ O (1), ດັ່ງນັ້ນພວກເຮົາຕ້ອງການແຜນທີ່. ແຕ່ ສຳ ລັບວິທີການ getRandom (), ພວກເຮົາຕ້ອງການໂຄງສ້າງຂໍ້ມູນທີ່ອີງໃສ່ດັດສະນີຄືກັບຂບວນດັ່ງນັ້ນພວກເຮົາສາມາດເລືອກເອົາອົງປະກອບດັດສະນີໃດ ໜຶ່ງ ເພື່ອກັບຄືນ.

ສະນັ້ນເພື່ອໃຫ້ໄດ້ທັງສາມ ໜ້າ ທີ່, ພວກເຮົາສາມາດ ນຳ ໃຊ້ທັງແຜນທີ່ແລະການວາງແຜນຮ່ວມກັນ. ເຮົາມາເບິ່ງກັນວ່າ

ຈຸດ ສຳ ຄັນ  

  1. ການແຊກໃສ່ໃນ array ແມ່ນ O (1) ຖ້າເຮັດຢູ່ທາງຫລັງ.
  2. ການລົບໃນອາເລແມ່ນ O (1) ຖ້າອົງປະກອບຖືກຍ້າຍອອກຈາກທາງຫລັງ.

ໂຄງສ້າງຂໍ້ມູນທີ່ ນຳ ໃຊ້  

ແຜນທີ່ M (ເພື່ອເກັບມູນຄ່າ, ຄູ່ດັດສະນີ)

Vector V ເພື່ອເກັບຮັກສາປັດຈຸບັນປັດຈຸບັນ

ສູດການຄິດໄລ່ ສຳ ລັບການແຊກ  

  1. ກວດເບິ່ງວ່າອົງປະກອບທີ່ມອບໃຫ້ມີຢູ່ໃນແຜນທີ່:
    • ຖ້າມີໃນປະຈຸບັນ, ຫຼັງຈາກນັ້ນໃຫ້ກັບຄືນມາປອມ
    • ອື່ນ:
      • ໃສ່ອົງປະກອບທີ່ໃຫ້ຢູ່ໃນຕອນທ້າຍຂອງ vector V
      • ໃສ່ອົງປະກອບທີ່ໃຫ້ໄວ້ແລະມັນເປັນດັດສະນີເພື່ອແຜນທີ່ M
      • ກັບຄືນມາເປັນຄວາມຈິງ

ສູດການຄິດໄລ່ການລຶບ  

  1. ກວດເບິ່ງວ່າອົງປະກອບທີ່ມອບໃຫ້ມີຢູ່ໃນແຜນທີ່:
    • ຖ້າມີຢູ່, ຫຼັງຈາກນັ້ນ:
      • ແລກປ່ຽນຄຸນຄ່າທີ່ໄດ້ຮັບແລະອົງປະກອບສຸດທ້າຍໃນ vector (ດັດສະນີສາມາດຊອກຫາໄດ້ໂດຍໃຊ້ແຜນທີ່ M)
      • ປັບປຸງແຜນທີ່ເປັນ M [last_element] = M [ມອບໃຫ້]
      • ລົບລ້າງອົງປະກອບສຸດທ້າຍຂອງ vector.
      • ລົບລ້າງອົງປະກອບທີ່ໃຫ້ຈາກແຜນທີ່
      • ກັບຄືນມາເປັນຄວາມຈິງ.
    • ອື່ນ, ກັບຄືນມາບໍ່ຖືກຕ້ອງ.
ເບິ່ງ
Palindromic ທີ່ຍາວທີ່ສຸດ

ສູດການຄິດໄລ່ ສຳ ລັບ getRandom  

  1. ເລືອກດັດຊະນີແບບສຸ່ມໃດ ໜຶ່ງ i
  2. n ລະດັບຂອງ 0 ເຖິງຂະ ໜາດ ຂອງ vector.
  3. ກັບມາປະຈຸບັນຢູ່ທີ່ດັດຊະນີນັ້ນໃນ vector V.

ການຈັດຕັ້ງປະຕິບັດ ສຳ ລັບການໃສ່ Delete Delete GetRandom  

ໂປຣແກຣມ C ++ ສຳ ລັບໃສ່ Delete Delete 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 ສຳ ລັບການແຊກ Delete 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

ເອກະສານ