Мэдээллийн бүтцийн зураг төсөл боловсруулах


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны DBOI Facebook-ийн Фанатикууд Фуркайт
Мэдээллийн бүтэц Онол

Мэдээллийн бүтцийн зураг төслийг сонсох нь олон хүмүүс гарчгийг өөрөө хараад зугтахыг хүсч магадгүй юм. Намайг мэддэг хүмүүс би үзэл баримтлалыг бүхэлд нь тайлбарлахаас нааш явахгүй гэдгээ мэддэг. Надтай хамт өнөөдрийн замд тулгарч буй бэрхшээл, цөөн хэдэн санааг сурах аялалд гараарай!

Бидний олонх нь “нэр томъёоны талаар санаа зовох байсан.CRUD "гэж бичсэн байна.Үүнийг мэдэхгүй хүмүүсийн хувьд CRUD нь унших шинэчлэлтийг устгах гэсэн үг юм.

Жишээ нь

Та үүсгэж байна Өгөгдлийн сан Таны хамгийн дуртай уран бүтээлчдийн

C-үүсгэх

  • Та шинэ уран бүтээлч нээгээд мэдээллийн санд оруулахыг хүсч байна гэж бодъё. Та оруулга үүсгэх болно.

Унших

  • Та хөгшин уран бүтээлчийн үгийг сонсохыг хүсч байна. Тиймээс та мэдээллийн сангаас өгөгдлийн оруулгыг унших болно.

U-шинэчлэх

  • Та Rihanna-г R&B-ийн оронд Pop-ийн доор оруулсан гэж андуураад алдаагаа засах хэрэгтэй. Тиймээс та шинэчлэх болно.

D-устгах

  • Та одоо Тори Келлиг сонсох дургүй. Тиймээс та оруулгыг устгах болно.

Өнөөдрийн асуудалд бид тэгэх ёстой “Мэдээллийн бүтцийг боловсруулах” Insert, Устгах, GetRandom аргуудыг гүйцэтгэдэг.

Оруулах:

Одоо байгаа өгөгдлийн бүтцэд элемент нэмэх

Устгаж байна:

Бид өгөгдлийн бүтцийг боловсруулахдаа элементийг хасах болно байгаа тохиолдолд л.

GetRandom:

Одоо байгаа шинж чанаруудын аль нэгийг нь сонгох магадлал ижил байгааг харгалзан санамсаргүй элементийг буцааж өгч байна.

Ашиглаж болох мэдээллийн бүтэц

Үйлдлийг гүйцэтгэх арга замын талаар бодохыг оролдохын зэрэгцээ олон өгөгдлийн бүтцийг авч үзэж болно. Элементүүдийг үр дүнтэй нэмэхийн тулд бид массив эсвэл LinkedList ашиглаж болно. Гэсэн хэдий ч LinkedList ба Arrays хоёулаа устгах үйлдлийг O (1) хугацаанд хийх чадваргүй тул биднийг өөр өгөгдлийн бүтэц рүү хөтөлж байна. Хэш газрын зураг.

Хэш газрын зураг нь өгөгдлийг нэмж, индексийн дагуу санамсаргүй өгөгдөл авах боломжтой бол сэвшээ салхи болж хувирна. Гэсэн хэдий ч өгөгдлийн цэгүүдийг тодорхой утгатай устгахыг хичээх нь нэлээд даалгавар болно.

Шаардлагатай бол шинэ бүтээлийн эх бөгөөд бидний нөхцөл байдал биднийг шинэ эрлийз рүү хөтөлдөг

Энэ хандлагын хувьд бид эрлийз болно

HashMap + ArrayList (Аливаа уян хатан цуглуулгын хүрээ ашиглаж болно, өөрөөр хэлбэл Set, Vector, гэх мэт).

Бүх аргуудын товч агуулгыг танилцуулж, тэдгээрийг хэрхэн нөхцөлд тохируулан зохиож болох талаар танилцуулъя

Оруулах арга

  • Бид массив болон HashMap аль алинд нь үнэт зүйлсээ оруулдаг
  • Хэрэв утга аль хэдийн орсон бол бид худал утгыг буцаана

Арга арилгах

  • Энэ бол ArrayList бидэнд бодит тусламж үзүүлдэг
    • Бид getray аргаар ArrayList-ээс элементийн байрлалыг авдаг
    • ArrayList-ийн хамгийн сүүлийн байрлал дээрх элементийг тохируулаарай
    • Хамгийн сүүлчийн элементийг арилгах элементийн байрлал дээр тавьдаг
    • Дараа нь уг элементийг hashmap болон ArrayList хоёулангаас нь хасах болно
    •  Хэмжээ нь багассан
  • Хэрэв элемент байхгүй бол бид худал утгыг буцаана

GetRandom арга

  • Бид санамсаргүй тоо үүсгэхийн тулд Java болон C ++ дээр суурилсан санамсаргүй аргыг ашигладаг
  • Бид тухайн байрлал дахь элементийг буцааж өгдөг
Мэдээллийн бүтцийн зураг төсөл боловсруулах
Асуудалд зориулж боловсруулсан эрлийз өгөгдлийн бүтэц

Өгөгдсөн бүтцийн хувьд Java код

class RandomizedSet
{

    /** Initialize your data structure here. */
    HashMap<Integer,Integer>hash;
    ArrayList<Integer>store;
    java.util.Random rand=new java.util.Random();
    public RandomizedSet()
    {
     hash=new HashMap<Integer,Integer>();
     store=new ArrayList<Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) 
    {
        if(hash.containsKey(val))
            return false;
        else
        {
        hash.put(val,store.size());
        store.add(val);   
        }
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) 
    {
       if(!hash.containsKey(val))
           return false;
        else
        {
        int cur_pos=store.get(val);
        int last=store.get(store.size()-1);
        store.set(cur_pos,last);
        hash.put(last,cur_pos);
        store.remove(val);
        hash.remove(store.size()-1);   
        }
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() 
    {
       return store.get(rand.nextInt(store.size())); 
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Өгөгдсөн өгөгдлийн бүтцэд зориулсан C ++ код

#include<time.h>
class RandomizedSet {
public:
    /** Initialize your data structure here. */
    map<int,int>hash;
    vector<int>store;
    int size=0;
    RandomizedSet() {
        size=0;
        srand(time(0));
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(hash.find(val)!=hash.end())
            return false;
        if (store.size() == size)
            store.push_back(val);
        else
        store[size]=val;
        hash.insert({val,size});
        size++;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        auto srch=hash.find(val);
        if(hash.find(val)==hash.end())
            return false;
        int ele=(*srch).second;
        if(size>1)
        {
            store[ele]=store[size-1];
            (*hash.find(store[size-1])).second=ele;
        }
        size--;
        hash.erase(val);
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        if(size==1)
            return store[0];
        return store[rand()%size];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */
["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]
[null,true,false,true,2,true,false,2]

Өгөгдлийн бүтцийн цаг хугацааны нарийн төвөгтэй байдал

Оруулах: O (1) нь HashMap ба ArrayList хоёуланд нь O (1)

GetRandom: O (1) .HashMap өгөгдөл буцаахад O (1) хугацаа шаардагдана

Устгах O (n).

Бид өгөгдлийг hashmap-аас O (1) цагт устгадаг боловч урьдчилсан боловсруулалт O (N) цагийг шаарддаг. ArrayList дэх индексийг авах үйл ажиллагаа нь O (n) байх тул.

Ашигласан материал