Dizayn Skiplist LeetCode Həll

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Verilənlər bazası eBay Facebook google microsoft cuqquldamaq
PureStorageBaxılıb 17

Problem bəyanat

Dizayn Skiplist LeetCode Həlli – Dizayn a Skiplist heç bir daxili kitabxanadan istifadə etmədən.

A siyahını atın alan məlumat strukturudur O(log(n)) əlavə etmək, silmək və axtarmaq vaxtıdır. Eyni funksiyaya və performansa malik olan ağac və qırmızı-qara ağac ilə müqayisədə, Skiplist-in kod uzunluğu nisbətən qısa ola bilər və Skip siyahılarının arxasındakı fikir sadəcə sadə əlaqəli siyahılardır.

Məsələn, bizdə olan Skiplist var [30,40,50,60,70,90] və əlavə etmək istəyirik 80 və 45 onun içinə. Skiplist bu şəkildə işləyir:

Dizayn Skiplist LeetCode HəllPin

Siz skiplistdə bir çox təbəqənin olduğunu görə bilərsiniz. Hər bir təbəqə sıralanmış əlaqəli siyahıdır. Üst təbəqələrin köməyi ilə əlavə etmək, silmək və axtarışdan daha sürətli ola bilər O(n). Sübut edilə bilər ki, hər bir əməliyyat üçün orta vaxt mürəkkəbliyi O(log(n)) və kosmik mürəkkəblikdir O(n).

Skiplist haqqında daha çox məlumat əldə edin: https://en.wikipedia.org/wiki/Skip_list

Həyata keçirir Skiplist sinif:

  • Skiplist() Skiplist obyektini işə salır.
  • bool search(int target) Yekunları true tam ədəd olarsa target Skiplist-də mövcuddur və ya false başqa cür.
  • void add(int num) Dəyəri daxil edir num SkipList-ə daxil edin.
  • bool erase(int num) Dəyəri silir num Skiplist-dən və qaytarır true. Əgər num Skiplist-də yoxdur, heç nə etmə və geri qayıt false. Çoxlu varsa num dəyərlər, onlardan hər hansı birini silmək yaxşıdır.

Qeyd edək ki, Skiplist-də dublikatlar ola bilər, kodunuz bu vəziyyəti idarə etməlidir.

Input
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
Output
[null, null, null, null, false, null, true, false, true, false]

Explanation
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0); // return False
skiplist.add(4);
skiplist.search(1); // return True
skiplist.erase(0);  // return False, 0 is not in skiplist.
skiplist.erase(1);  // return True
skiplist.search(1); // return False, 1 has already been erased.

Izahat

Skip siyahıları alternativdir taraz ağaclar və ya özünü tənzimləyən ağaclar və onların həyata keçirilməsi RB və ya AVL ağaclarından daha asandır. Təsadüfi ədədlər generatoru ilə məsləhətləşərək balanslaşdırılırlar. Bu kodda mən rand() istifadə edirəm.

Əvvəlcədən təqdim edilməyən n (skiplistə əlavə olunacaq elementlərin sayı) bilsək, bu kodu təkmilləşdirmək olar. Bu məlumatla maksimum səviyyəni tapmaq asan olardı – deyək ki, 32K element üçün maksimum 15 səviyyəyə malik ola bilərik (2^15 = 32K). Təsadüfi olaraq qurduğumuz ara sütunlar bu maksimum səviyyə ilə məhdudlaşdırıla bilər. Həmçinin, bu kodda biz sütunların qaldırılmasını məhdudlaşdırmırıq – onlar 0 səviyyəsində element daxil edərkən qaldırıla bilər. Beləliklə, bir təkmilləşdirmə sütunu təsadüfi qaldırmamaq və bunu 0 səviyyəsində hər m qovşaq üçün etmək olardı. .

Level 5:

Level 4:------->3---->NULL

Level 3:------->3---->NULL

Level 2:------->3---->NULL

Level 1:---->2->3->4->NULL

Level 0:->1->2->3->4->NULL

Kodu

Dizayn Skiplist üçün C++ Kodu

class Skiplist {
private:
    struct sle { int val; sle *down, *next; };
    vector<sle *> head;
    int level = 0;
    
    /* Debugging - visualize how the skip list looks */
    void visual(void) {
        for (int i = level; i >= 0; i--) {
            sle *p = head[i];
            cout << "Level " << i << ":";
            while(p) { if (p->val >= 0) cout << p->val << " "; p = p->next; }
            cout << endl;
        }
    }

public:
    Skiplist() {
        return;
    }

    bool search(int target) {
        sle *p = head[level];   /* start from the highest level */
        while (p) {
            if (p->val == target) return 1; /* found */
            /* If the next node is higher than target, descend down the column to lower level */
            if (p->next == NULL || (p->next && p->next->val > target)) { p = p->down; continue; }
            p = p->next;
        }
        return 0;
    }
    
    void add(int num) {
        int l = 0 /* start at level 0 */, once = 0;     /* at least one loop is required */ 
        sle *ln = NULL;                                 /* last lower node */
        while (!once++ || (rand() % 2)) {               /* at least once OR as long as coin flip is 1 */
            sle *n = new sle; n->val = num, n->down = ln, n->next = NULL;   /* allocate a skip list entry node, 
                                                        /* with down pointing to node in this column at level below */
            
            /* First time init of skip list - add a sentinel node and the new node */
            if (head.size() == 0) {                     
                sle *sn/*sentinel node */ = new sle; sn->val = INT_MIN, sn->next = n, sn->down = NULL;
                head.push_back(sn); return; 
            }
            
            /* Insert node at level l */
            sle *p = head[l], *last = NULL;
            while (p) { if (p->val >= num) { last->next = n; n->next = p; break; } last = p; p = p->next; }
            if (!p) last->next = n;

            /* We need one more level - promote the sentinel node to new level */
            if (++l > level) {
                sle *sn/*sentinel node */ = new sle; sn->val = INT_MIN; sn->next = NULL; sn->down = head[level];
                head.push_back(sn); 
                level++;
            }
            
            /* Record node at this level to be used for down field of node at upper level */
            ln = n;
        }
    }
    
    bool erase(int num) {
        sle *p = head[level]; /* start at highest level */ bool del = 0;
        while (p) {
            /* If next node is end of list or is greater than num, descend down the column */
            if (p->next == NULL || p->next->val > num) { p = p->down; continue; }
            
            /* if found, delete it at this level and continue on to next lower level */
            if (p->next && p->next->val == num) {   
                p->next = p->next->next; 
                del = 1; 
                p = p->down; continue; 
            }
            p = p->next;
        }
        return del;
    }
};

Dizayn Skiplist üçün Java Kodu

class Skiplist {
    class Node {
        int val;
        Node next, down;
        public Node(int val, Node next, Node down) {
            this.val = val;
            this.next = next;
            this.down = down;
        }
    }
    Node head = new Node(-1, null, null);
    Random rand = new Random();
    public Skiplist() {
        
    }
    
    public boolean search(int target) {
        Node cur = head;
        while (cur != null) {
            while (cur.next != null && cur.next.val < target) {
                cur = cur.next;
            }
            if (cur.next != null && cur.next.val == target) return true;
            cur = cur.down;
        }
        return false;
    }
    
    public void add(int num) {
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur != null) {
            while (cur.next != null && cur.next.val < num) {
                cur = cur.next;
            }
            stack.push(cur);
            cur = cur.down;
        }
        boolean insert = true;
        Node down = null;
        while (insert && !stack.isEmpty()) {
            cur = stack.pop();
            cur.next = new Node(num, cur.next, down);
            down = cur.next;
            insert = rand.nextDouble() < 0.5;
        }
        if (insert) head = new Node(-1, null, head);
    }
    
    public boolean erase(int num) {
        Node cur = head;
        boolean found = false;
        while (cur != null) {
            while (cur.next != null && cur.next.val < num) {
                cur = cur.next;
            }
            if (cur.next != null && cur.next.val == num) {
                found = true;
                cur.next = cur.next.next;
            }
            cur = cur.down;
        }
        return found;
    }
}

Dizayn Skiplist LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O(log n) əlavə etmək, axtarmaq və silmək üçün.

Kosmik Mürəkkəblik

O (səviyyələr * hər_səviyyəyə_seqmentlərin_sayı)

 

Translate »