வரிசைப்படுத்தப்பட்ட பட்டியல் 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 அல்ல என்பதால் நகல் அல்லாதது என்று சொல்கிறோம்.

எனவே, இதை சுருக்கமாக. நாங்கள் பட்டியலைக் கடந்து செல்கிறோம். அடுத்த உறுப்பு தற்போதைய உறுப்புக்கு சமமானதா என சோதித்துக்கொண்டே இருங்கள். அது நடந்தால், நகல் அல்லாத உறுப்பைக் கண்டுபிடிக்கும் வரை உறுப்புகளை அகற்றிக் கொண்டே இருங்கள்.

குறியீடு

வரிசைப்படுத்தப்பட்ட பட்டியல் 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), ஏனென்றால் நாம் உறுப்புகளில் சரியாக ஒன்றைக் கடந்து செல்கிறோம். இதனால் நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (1), ஏனெனில் நாங்கள் நிலையான கூறுகளைப் பயன்படுத்தினோம். இதனால் விண்வெளி சிக்கலானது நிலையானது.