Dublikatları Sıralanmış Siyahı II-dən silin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon
Bağlı siyahıBaxılıb 87

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem "Sıralanmış Siyahıdan Dublikatları Sil", sizə təkrarlanan elementlərə sahib ola bilən və ya olmaya bilən əlaqəli bir siyahının verildiyini bildirir. Siyahıda təkrarlanan elementlər varsa, bütün nümunələrini siyahıdan silin. Aşağıdakı əməliyyatları yerinə yetirdikdən sonra, əlaqəli siyahını sonunda çap edin.

misal

Dublikatları Sıralanmış Siyahı II-dən silinPin

Elements of linked list: 1 2 2 2 3 5 7 7
List after removing all the elements: 1 3 5

Izahat

2 rəqəminin siyahıda 3 nümunəsi var. Beləliklə, bütün nümunələrini qaldırdıq. Eyni şey 7 rəqəmi ilə də baş verdi. Beləliklə, 2 və 7 nümunələrinin hamısını götürdükdən sonra bizə yalnız 3 1 3 olan 5 element qaldı.

Yanaşma

Artıq qeyd edildiyi kimi “Dublikatları Sıralanmış Siyahıdan II çıxarın” problemi, siyahıda mövcud olan dublikatları olan bütün nömrələri silməyimizi xahiş edir. Bir dəfə müzakirə olunan bir problem var idi. Ancaq mövcud problemdə cüzi bir fərq var. Əvvəlki problem istədi yalnız dublikatları silin. Yəni dublikatları sildik, ancaq dublikatları olan elementin tək bir nüsxəsi silinmədi. Burada siyahıda dublikatları olan hər nüsxəni və orijinal elementi silmək məcburiyyətindəyik.

Beləliklə, indi problemlə tanışıq. Problemi həll etməyin yollarını düşünə bilərik. Artıq siyahının sıralandığını bilirik. Beləliklə, bu həqiqətdən istifadə edə bilərik. Siyahı sıralanırsa, əminik ki, hər hansı bir dublikat varsa. Həmişə bir qrup halında olurlar. Beləliklə, bitişik elementləri təkrarlamaq üçün yoxlamalıyıq. Belə bir cütə rast gəlsək. Əvvəlcə, təkrarlanmayan bir element tapana və ya siyahı bitənə qədər siyahıdan keçirik. O nöqtədə əvvəlki qovluğu bu yeni təkrarlanmayan elementə yönəldirik. Sonra yenidən bu təkrarlanmayan elementdən təkrarlanan elementləri axtarmağa başlayın.

"Dublikat olmayan" ifadəsi ilə, cari elementin siyahıda heç bir dublikat olmadığını ifadə etmirik. Yalnız cari düyünün bu elementə bərabər olmadığı deməkdir. Fikir verin, siyahıda 1, 2, 2, 2, 3, 3 var. 1 ilə 3 arasındayıq. Lakin 3 də silinəcəkdir. Ancaq bir müddət, bitişik elementləri yoxlayarkən ilk 2 2 cütə rast gəldikdə. 3-ün təkrarlanmayan olduğunu deyirik, çünki 2 deyil.

Beləliklə, bunu ümumiləşdirmək üçün. Sadəcə siyahıdan keçirik. Növbəti elementin cari elementlə eyni olub olmadığını yoxlamağa davam edin. Əgər bu baş verərsə, təkrarlanmayan bir element tapana qədər elementləri götürməyə davam edin.

Kodu

Dublikatları Sıralanmış Siyahı II-dən çıxarmaq üçün C ++ kodu

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

ListNode* deleteDuplicates(ListNode* head) {
    if(head==NULL || head->next==NULL)
        return head;
    ListNode* prev = create(-1);
    ListNode* dummy = prev;
    ListNode* cur = head;
    prev->next = cur;
    while(cur && cur->next) {
        if(cur->data == cur->next->data) {
            while(cur->next && cur->data==cur->next->data) {
                ListNode* tmp = cur;
                cur = cur->next;
                free(tmp);
            }
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return dummy->next;
}

void printLinkedList(ListNode *headA){
  while(headA != NULL){
    cout<<headA->data<<" ";
    headA = headA->next;
  }
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  headA->next->next = create(2);
  headA->next->next->next = create(2);
  headA->next->next->next->next = create(3);
  headA->next->next->next->next->next = create(5);
  headA->next->next->next->next->next->next = create(7);
  headA->next->next->next->next->next->next->next = create(7);

  headA = deleteDuplicates(headA);
  printLinkedList(headA);
}
1 3 5

Dublikatların Sıralanmış Siyahı II-dən çıxarılması üçün Java kodu

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

  static ListNode deleteDuplicates(ListNode head) {
      if(head==null || head.next==null)
          return head;
      ListNode prev = create(-1);
      ListNode dummy = prev;
      ListNode cur = head;
      prev.next = cur;
      while(cur != null && cur.next != null) {
          if(cur.data == cur.next.data) {
              while(cur.next != null && cur.data==cur.next.data) {
                  ListNode tmp = cur;
                  cur = cur.next;
              }
              prev.next = cur.next;
              cur = prev.next;
          } else {
              prev = cur;
              cur = cur.next;
          }
      }
      return dummy.next;
  }

  static void printLinkedList(ListNode headA){
    while(headA != null){
      System.out.print(headA.data+" ");
      headA = headA.next;
    }
  }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    headA.next.next = create(2);
    headA.next.next.next = create(2);
    headA.next.next.next.next = create(3);
    headA.next.next.next.next.next = create(5);
    headA.next.next.next.next.next.next = create(7);
    headA.next.next.next.next.next.next.next = create(7);

    headA = deleteDuplicates(headA);
    printLinkedList(headA);
  }
}
1 3 5

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki elementləri tam olaraq bir dənə keçirik. Beləliklə, zamanın mürəkkəbliyi doğrudur.

Kosmik Mürəkkəblik

O (1), çünki daimi elementlərdən istifadə etdik. Beləliklə kosmik mürəkkəblik sabitdir.

Crack Sistemi Dizayn Müsahibələri
Translate »