ವಿಂಗಡಿಸಲಾದ ಪಟ್ಟಿ 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), ಏಕೆಂದರೆ ನಾವು ಸ್ಥಿರ ಅಂಶಗಳನ್ನು ಬಳಸಿದ್ದೇವೆ. ಹೀಗಾಗಿ ಜಾಗದ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.