موارد تکراری را از فهرست مرتب سازی شده II حذف کنید


سطح دشواری متوسط
اغلب در آمازون
لینک شده

مشکل "حذف موارد تکراری از لیست مرتب سازی شده II" بیان می کند که یک لیست پیوندی به شما داده می شود که ممکن است عناصر تکراری داشته باشد یا نداشته باشد. اگر لیست عناصر تکراری دارد ، همه موارد آنها را از لیست حذف کنید. پس از انجام عملیات زیر ، لیست پیوندی را در انتها چاپ کنید.

مثال

موارد تکراری را از فهرست مرتب سازی شده II حذف کنید

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

توضیح

عدد 2 دارای 3 نمونه در لیست است. بنابراین ما همه موارد آن را حذف کردیم. همین امر با شماره 7 اتفاق افتاد. بنابراین پس از حذف همه نمونه های 2 و 7. ما فقط 3 عنصر که 1 3 5 هستند باقی مانده است.

روش

همانطور که قبلاً گفته شد ، مسئله "حذف کپی ها از فهرست مرتب سازی شده II" از ما می خواهد که تمام اعدادی را که دارای کپی هستند ، حذف کنیم. یک بار مشکلی پیش آمد اما تفاوت کمی در مسئله فعلی وجود دارد. مشکل قبلی از ما خواست فقط موارد تکراری را حذف کنید. یعنی ما نسخه های کپی را حذف کردیم اما یک نسخه از عناصر موجود در آن حذف نشد. در اینجا ما باید هر نسخه و عنصر اصلی را که نسخه های تکراری آن در لیست وجود دارد ، حذف کنیم.

بنابراین ، اکنون با مشکل آشنا شده ایم. ما می توانیم راه حل هایی برای حل این مشکل بیندیشیم. ما قبلاً می دانیم که لیست مرتب شده است. بنابراین می توانیم از این واقعیت استفاده کنیم. اگر لیست مرتب شده باشد ، مطمئن هستیم که نسخه کپی وجود دارد. آنها همیشه در یک گروه اتفاق می افتند. بنابراین ، ما فقط باید عناصر مجاور را برای موارد تکراری بررسی کنیم. اگر به چنین جفتی برخوردیم. ابتدا لیست را پیمایش می کنیم تا زمانی که یک عنصر غیر تکراری را پیدا کنیم یا لیست به پایان برسد. در آن مرحله ، گره قبلی را به سمت این عنصر جدید غیر تکراری نشان می دهیم. سپس دوباره شروع به جستجوی عناصر تکراری از این عنصر غیر تکراری کنید.

منظور ما از اصطلاح "غیر کپی" این نیست که عنصر فعلی هیچ کپی در لیست ندارد. این فقط به این معنی است که گره فعلی با این عنصر برابر نیست. در نظر بگیرید ، ما 1 ، 2 ، 2 ، 2 ، 3 ، 3 در لیست داریم. ما 1 به 3 را نشان می دهیم. با این حال ، 3 نیز حذف می شود. اما در برهه ای از زمان ، وقتی داشتیم عناصر مجاور را بررسی می کردیم و با 2 2 جفت اول مواجه شدیم. می گوییم 3 غیر کپی است زیرا 2 نیست.

بنابراین ، به طور خلاصه این ما به سادگی لیست را رد می کنیم. و همچنان بررسی کنید که آیا عنصر بعدی همان عنصر فعلی است یا خیر. اگر چنین اتفاقی افتاد ، همچنان عناصر را حذف کنید تا یک عنصر غیر تکراری پیدا کنید.

رمز

کد ++ C برای حذف موارد تکراری از لیست مرتب شده II

#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

کد جاوا برای حذف موارد تکراری از فهرست مرتب سازی شده II

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

تحلیل پیچیدگی

پیچیدگی زمان

بر)، زیرا ما دقیقاً یک عنصر را رد می کنیم. بنابراین پیچیدگی زمان خطی است.

پیچیدگی فضا

O (1) ، زیرا ما از عناصر ثابت استفاده کرده ایم. بنابراین پیچیدگی فضا ثابت است.