Sorted List II LeetCode Solution-dan Dublikatları silin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Facebook google microsoftBaxılıb 21

Problem bəyanat

Çeşidlənmiş Siyahıdan Dublikatları Sil II LeetCode Həll – Nəzərə alınmaqla head sıralanır əlaqəli siyahıolan bütün qovşaqları silin dublikat orijinal siyahıdan yalnız fərqli nömrələr buraxaraq nömrələr. Qaytar əlaqəli siyahı sıralandı həmçinin.

Sorted List II LeetCode Solution-dan Dublikatları silinPin

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Izahat

Buradakı fikir, əlaqəli siyahımızı keçmək və iki göstəricidən istifadə etməkdir:

  1. slow təkrarlamalar başlamazdan əvvəl qovşaq üçündür
  2. fast təkrarlama qrupunun son qovşağı üçündür.

İndi qovşaqları keçərək aşağıdakı addımları yerinə yetiririk:

  1. bizdə isə fast.next və onun dəyəri bərabərdir fast, bu o deməkdir ki, daha bir dublikatımız var, ona görə də hərəkət edirik fast göstərici sağa.
  2. Əgər baş verərsə, o slow.next bərabərdir fast, o deməkdir ki, bizdə yalnız 1 təkrarlanan elementlər qrupunun elementi, yəni onu silməyimiz lazım deyil və hər iki göstəricini sağa köçürürük.
  3. Əgər baş verərsə, o slow.next ilə bərabər deyil fast, bu o deməkdir ki, bir qrup təkrarlanan elementləri atlamalıyıq: yeni bir əlaqə yaradırıq: slow.next = fast.next, həm də biz ayırırıq fast = slow.next. Qeyd edək ki, indi bizdə orijinal mülk var: slow təkrarlanan elementlər qrupundan əvvəl qovşağı göstərir və fast bu qrupun son elementi olacaq (sonra while fast.next and fast.val == fast.next.val: xətt)

Mürəkkəblik: zaman mürəkkəbliyidir O(n): hər bir göstərici üçün siyahımızı ən çox iki dəfə çeviririk. Kosmos mürəkkəbliyidir O(1): biz burada heç bir əlavə yaddaşdan istifadə etmədik.

Kodu

Sorted Siyahıdan Dublikatları Silmək üçün C++ Kodu II

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = dummy;
        int duplicate;
        while (cur->next && cur->next->next) {
            if (cur->next->val == cur->next->next->val) {
                duplicate = cur->next->val;
                while (cur->next && cur->next->val == duplicate) {
                    cur->next = cur->next->next;
                }
            }
            else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

Sorted Siyahıdan Dublikatları Silmək üçün Java Kodu II

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return null;
        ListNode FakeHead=new ListNode(0);
        FakeHead.next=head;
        ListNode pre=FakeHead;
        ListNode cur=head;
        while(cur!=null){
            while(cur.next!=null&&cur.val==cur.next.val){
                cur=cur.next;
            }
            if(pre.next==cur){
                pre=pre.next;
            }
            else{
                pre.next=cur.next;
            }
            cur=cur.next;
        }
        return FakeHead.next;
    }
}

Sorted Siyahıdan Dublikatları Silmək üçün Python Kodu II

class Solution:
    def deleteDuplicates(self, head):
        dummy = ListNode(-1)
        dummy.next = head
        fast, slow = head, dummy
        while fast:
            while fast.next and fast.val == fast.next.val:
                fast = fast.next
            if slow.next == fast:
                slow, fast = slow.next, fast.next
            else:
                slow.next = fast.next
                fast = slow.next
                
        return dummy.next

Sorted Siyahıdan Dublikatları Silmək üçün Mürəkkəblik Təhlili II LeetCode Həll

Zamanın mürəkkəbliyi

O (N)

Kosmik Mürəkkəblik

O (1)

Translate »