طراحی ساختار داده


سطح دشواری متوسط
اغلب در آمازون DBOI فیس بوک متعصبان فورکایت
ساختار داده ها نظریه

با گوش دادن به طراحی ساختار داده ، بسیاری از افراد ممکن است بخواهند با دیدن خود عنوان فرار کنند. کسانی که من را می شناسند می دانند که من تا زمانی که مفهوم را به طور کامل توضیح ندهم ، آنجا را ترک نمی کنم. با من همراه شوید و یک مشکل و چند ایده در راه امروز خود بیاموزید!

بسیاری از ما در مورد اصطلاح "چیز چندش و کثیف".CRUD برای کسانی که آن را نمی دانند مخفف ایجاد خوانده شده بروزرسانی حذف است.

مثال

شما در حال ایجاد یک هستید پایگاه داده از همه هنرمندان مورد علاقه شما

C ایجاد کنید

  • بیایید بگوییم شما یک هنرمند جدید کشف کرده اید و می خواهید آن را در پایگاه داده قرار دهید. شما در حال ایجاد یک ورودی هستید.

R-Read

  • شما می خواهید به یک هنرمند قدیمی گوش دهید. بنابراین ، شما یک ورودی داده را از پایگاه داده می خوانید.

U-Update

  • شما به اشتباه ریحانا را به جای R&B زیر پاپ قرار داده اید و باید اشتباه خود را اصلاح کنید. بنابراین ، شما به روز می کنید.

D- حذف کنید

  • دیگر دوست ندارید به توری کلی گوش دهید. بنابراین شما ورودی را حذف می کنید.

در مشکل امروز ، ما باید "طراحی یک ساختار داده" که روش های Insert ، Delete و GetRandom را انجام می دهد.

درج:

افزودن عنصری به ساختار داده موجود

حذف:

همانطور که در حال طراحی ساختار داده هستیم ، عنصر را حذف خواهیم کرد فقط در صورت وجود

GetRandom:

با توجه به اینکه احتمال انتخاب هر یک از ویژگی های موجود یکسان است ، من یک عنصر تصادفی را برمی گردانم.

ساختار داده ای که می تواند مورد استفاده قرار گیرد

هنگام تلاش برای اندیشیدن راهی برای انجام عملیات ، می توان مجموعه ای از ساختار داده را در نظر گرفت. برای افزودن کارآمد عناصر می توانیم از آرایه ها یا LinkedList استفاده کنیم. با این حال ، LinkedList و Arrays هر دو قادر به انجام عملیات حذف در زمان O (1) نیستند که ما را به یک ساختار داده دیگر می رساند. نقشه های هاش

در حالی که Hash Maps می تواند اضافه کردن داده ها و به دست آوردن داده های تصادفی را براساس شاخص تبدیل کند. با این حال ، تلاش برای حذف نقاط داده با مقادیر خاص کاملاً یک وظیفه است.

ضرورت مادر اختراع است و شرایط ما را به سمت ترکیبی جدید سوق می دهد

در روش داده شده ما ترکیبی از

HashMap + ArrayList (هر چارچوب مجموعه انعطاف پذیر را می توان استفاده کرد ، به عنوان مثال Set ، Vector و غیره)

بگذارید خلاصه ای از همه روش ها و چگونگی طراحی آنها متناسب با شرایط را ارائه دهم

درج روش

  • مقادیر خود را هم در آرایه و هم در HashMap وارد می کنیم
  • اگر مقدار از قبل موجود باشد ، نادرست برمی گردانیم

حذف روش

  • اینجاست که ArrayList به ما کمک واقعی می کند
    • ما موقعیت عنصر را از ArrayList با روش get دریافت می کنیم
    • با قرار دادن عنصر روی آخرین موقعیت در ArrayList
    • عنصر از آخرین در موقعیت عنصر قرار داده می شود حذف شود
    • سپس این عنصر از هر دو برنامه hashmap و ArrayList حذف می شود
    •  اندازه کاهش می یابد
  • اگر این عنصر وجود نداشته باشد ، نادرست برمی گردیم

روش GetRandom

  • ما برای تولید یک عدد تصادفی از روش تصادفی داخلی در جاوا و C ++ استفاده می کنیم
  • عنصر را در آن موقعیت برمی گردانیم
طراحی ساختار داده
ساختار داده ترکیبی برای این مشکل طراحی شده است

کد جاوا برای داده داده شده ساختار

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) از hashmap حذف می کنیم ، اما پیش پردازش برای O (N) فراخوانی می شود. از آنجا که عملیات به دست آوردن این شاخص در ArrayList O (n) است.

منابع