យកស្ទួនចេញពីបញ្ជីតម្រៀបទី ២


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon
បញ្ជីភ្ជាប់

បញ្ហា“ យកស្ទួនចេញពីបញ្ជីតម្រៀបទី ២” ចែងថាអ្នកត្រូវបានផ្តល់បញ្ជីដែលបានភ្ជាប់ដែលអាចឬមិនមានធាតុស្ទួន។ ប្រសិនបើបញ្ជីមានធាតុស្ទួនបន្ទាប់មកដកវត្ថុទាំងអស់ចេញពីបញ្ជី។ បន្ទាប់ពីអនុវត្តប្រតិបត្តិការដូចខាងក្រោមបោះពុម្ពបញ្ជីភ្ជាប់នៅចុងបញ្ចប់។

ឧទាហរណ៍

យកស្ទួនចេញពីបញ្ជីតម្រៀបទី ២

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

ការពន្យល់

លេខ ២ មាន ៣ ករណីនៅក្នុងបញ្ជី។ ដូច្នេះយើងបានដកហូតវត្ថុទាំងអស់របស់វា។ ដូចគ្នានឹងលេខ ៧ ដែរ។ ដូច្នេះបន្ទាប់ពីបានដកហូតវត្ថុទាំងអស់នៃលេខ ២ និងលេខ ៧ ។ យើងនៅសល់មានតែធាតុ ៣ ដែលជា ១ ៣ ៥ ។

វិធីសាស្រ្ត

បញ្ហា“ យកស្ទួនចេញពីបញ្ជីតម្រៀបទី ២” ដូចដែលបានបញ្ជាក់រួចហើយស្នើសុំឱ្យយើងលុបលេខទាំងអស់ដែលស្ទួនចេញនៅក្នុងបញ្ជី។ មានបញ្ហាមួយដែលត្រូវបានពិភាក្សាម្តងហើយម្តងទៀត។ ប៉ុន្តែមានភាពខុសគ្នាបន្តិចបន្តួចនៅក្នុងបញ្ហាបច្ចុប្បន្ន។ បញ្ហាមុនបានសួរយើង លុបតែស្ទួន។ នោះគឺយើងបានលុបស្ទួនគ្នាប៉ុន្តែច្បាប់ចម្លងនៃធាតុដែលស្ទួនមានវត្តមានមិនត្រូវបានដកចេញទេ។ នៅទីនេះយើងត្រូវលុបរាល់ឯកសារថតចម្លងនិងធាតុដើមក៏ដូចជាឯកសារចម្លងរបស់វានៅក្នុងបញ្ជី។

ដូច្នេះឥឡូវនេះយើងស៊ាំនឹងបញ្ហាហើយ។ យើងអាចគិតពីវិធីដើម្បីដោះស្រាយបញ្ហា។ យើងដឹងរួចហើយថាបញ្ជីត្រូវបានតម្រៀប។ ដូច្នេះយើងអាចប្រើការពិតនេះ។ ប្រសិនបើបញ្ជីត្រូវបានតម្រៀបយើងប្រាកដថាប្រសិនបើមានលេខស្ទួនណាមួយ។ ពួកគេតែងតែកើតឡើងជាក្រុម។ ដូច្នេះយើងគ្រាន់តែត្រូវការពិនិត្យមើលធាតុដែលនៅជាប់គ្នាសម្រាប់ការចម្លង។ ប្រសិនបើយើងឆ្លងកាត់គូបែបនេះ។ ដំបូងយើងឆ្លងកាត់បញ្ជីឈ្មោះរហូតដល់យើងរកឃើញធាតុមិនចម្លងឬបញ្ជីបញ្ចប់។ នៅចំណុចនោះយើងចង្អុលថ្នាំងពីមុនទៅធាតុមិនចម្លងថ្មីនេះ។ បន្ទាប់មកចាប់ផ្តើមស្វែងរកធាតុស្ទួនពីធាតុមិនស្ទួននេះ។

ដោយពាក្យថា "មិនចម្លង" យើងមិនមានន័យថាធាតុបច្ចុប្បន្នមិនមានលេខស្ទួនណាមួយនៅក្នុងបញ្ជីទេ។ វាគ្រាន់តែមានន័យថាថ្នាំងបច្ចុប្បន្នមិនស្មើនឹងធាតុនេះទេ។ ពិចារណាយើងមានលេខ ១ ២ ២ ៣ ៣ នៅក្នុងបញ្ជី។ យើងចង្អុលបង្ហាញពីលេខ ១ ដល់លេខ ៣។ ទោះជាយ៉ាងណាក៏ដោយលេខ ៣ ក៏នឹងត្រូវដកចេញដែរ។ ប៉ុន្តែនៅពេលណាមួយនៅពេលដែលយើងកំពុងពិនិត្យរកធាតុដែលនៅជិតគ្នាហើយបានឆ្លងកាត់ ២ ២ គូដំបូង។ យើងនិយាយថា ៣ មិនមែនជាលេខមួយស្ទួនទេព្រោះវាមិនមែនលេខ ២ ។

ដូច្នេះដើម្បីសង្ខេបរឿងនេះ។ យើងគ្រាន់តែឆ្លងកាត់បញ្ជី។ ហើយបន្តពិនិត្យមើលថាតើធាតុបន្ទាប់គឺដូចគ្នានឹងធាតុបច្ចុប្បន្នដែរឬទេ។ ប្រសិនបើរឿងនោះកើតឡើងសូមបន្តយកធាតុចេញរហូតដល់អ្នករកឃើញធាតុមិនចម្លង។

លេខកូដ

កូដ C ++ ដើម្បីយកស្ទួនចេញពីបញ្ជីតម្រៀបទី ២

#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

កូដចាវ៉ាដើម្បីយកចេញស្ទួនពីបញ្ជីតម្រៀបទី ២

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 (N), ដោយសារតែយើងកំពុងឆ្លងកាត់ធាតុមួយយ៉ាងពិតប្រាកដ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ដោយសារតែយើងបានប្រើធាតុថេរ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺថេរ។