Маалыматтардын структурасын долбоорлоо


Кыйынчылык деңгээли орто
Көп суралган Amazon DBOI Facebook динчилдер Fourkites
Маалыматтардын структурасы теория

Маалыматтардын структурасын иштеп чыгууну угуу, көптөгөн адамдар аталыштын өзүн карап качып кетиши мүмкүн. Мени билгендер түшүнүктү толугу менен түшүндүрмөйүнчө кетпей турганымды билишет. Бүгүнкү жолубузда бир көйгөйдү жана бир нече идеяларды билүү үчүн, мени менен саякатка чыгыңыз!

Көпчүлүгүбүз «CRUD "деген аталыштагы билдирүү жасады.Муну билбегендер үчүн CRUD окуу жаңыртуусун өчүрүү дегенди билдирет.

мисал

Сиз түзүп жатасыз маалыматтар базасы бардык сүйүктүү сүрөтчүлөрүнүн.

C-түзүү

  • Жаңы сүрөтчү таптыңыз жана аны маалымат базасына киргизгиңиз келди дейли. Сиз жазууну түзүп жатасыз.

R-Read

  • Эски сүрөтчүнүн сөзүн уккуң келет. Ошентип, маалымат базасынан маалыматтарды киргизүүнү окуп жатасыз.

U-жаңыртуу

  • Сиз Rihanna ны R&B ордуна Поптун ордуна жаңылыштык менен койдуңуз жана катаңызды оңдошуңуз керек. Ошентип, сиз жаңырасыз.

D-Delete

  • Сиз эми Тори Келлини укканды жактырбайсыз. Ошентип, сиз жазууну жок кыласыз.

Бүгүнкү көйгөйдө биз "Маалыматтардын структурасын иштеп чыгуу" Insert, Delete жана GetRandom Methods аткарган.

Кыстаруу:

Учурдагы маалымат структурасына элемент кошуу

Өчүрүү:

Берилиштер структурасын иштеп чыгууда, элементти алып салабыз бар болсо гана.

GetRandom:

Учурдагы өзгөчөлүктөрдүн бирин тандап алуу ыктымалдыгы бирдей экендигин эске алып, кокустук элементти кайтарып жатам.

Колдонула турган маалыматтардын структурасы

Операцияларды аткаруунун жолун ойлонуп жатканда, маалымат структураларынын көпчүлүгүн кароого болот. Элементтерди натыйжалуу кошуу үчүн биз массивдерди же LinkedListти колдоно алабыз. Бирок, LinkedList жана Arrays экөө тең O (1) убагында алып салуу операциясын жасай алышпайт, бул бизди башка маалымат структурасына алып келет. Hash Maps.

Хэш Карталар маалыматтарды кошуп, индекс боюнча кокустук маалыматтарды алса, шамал болуп калат. Бирок, белгилүү бир баалуулуктар менен маалымат пункттарын алып салуу аракети бир топ милдет болуп калат.

Зарылдык - бул ойлоп табуунун энеси жана биздин жагдайлар бизди жаңы гибридге алып барат

Берилген мамиледе биз гибридди алабыз

HashMap + ArrayList (Коллекциянын ар кандай ийкемдүү алкагын колдонсо болот, б.а. Set, Vector, ж.б.)

Бардык ыкмалардын кыскача баяндамасын жана аларды шарттарга ылайыктап кантип иштеп чыгууну сунуштайын

Insert Method

  • Массивге да, HashMapга да баалуулуктарыбызды киргизебиз
  • Эгер мурунтан эле маани камтылса, биз жалганды кайтарабыз

Методду алып салуу

  • Бул жерде ArrayList бизге чыныгы жардам берет
    • ArrayListтен элементтин ордун get методу менен алабыз
    • ArrayList тизмесиндеги акыркы позицияга коюлган элемент
    • Акыркы элемент алынып салынуучу элементтин ордуна коюлат
    • Андан кийин элемент хэшмаптан жана ArrayList тизмесинен алынып салынат
    •  Көлөмү кичирейтилген
  • Эгер элемент жок болсо, биз жалган деп жооп беребиз

GetRandom Method

  • Биз кокустук санды түзүү үчүн 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).

Хэшмаптагы маалыматтарды O (1) убакытта жок кылабыз, бирок алдын-ала иштеп чыгуу O (N) убакытты талап кылат. Индекс алуу аракети ArrayListте O (n) болуп саналат.

шилтемелер