นับองค์ประกอบความถี่ขั้นต่ำในรายการที่เชื่อมโยงใน C++

กำหนดให้งานคือการนับองค์ประกอบความถี่ต่ำสุดในรายการเชื่อมโยงที่กำหนดซึ่งมีองค์ประกอบที่ซ้ำกัน

รายการที่เชื่อมโยงคือโครงสร้างข้อมูลที่จัดเก็บข้อมูลในลำดับต่อเนื่อง เช่นเดียวกับรายการที่แต่ละองค์ประกอบเชื่อมโยงกับองค์ประกอบถัดไป

ความถี่ขององค์ประกอบในรายการที่เชื่อมโยงหมายถึงจำนวนครั้งที่องค์ประกอบเกิดขึ้นในรายการที่เชื่อมโยง ตามปัญหาเราต้องนับความถี่ต่ำสุดในรายการที่เชื่อมโยง

สมมติว่าเรามีรายการที่เชื่อมโยง 1, 1, 3, 1, 3, 4, 6; โดยที่ความถี่ต่ำสุดคือหนึ่ง ดังนั้นเราต้องนับองค์ประกอบที่มีความถี่ต่ำสุด มีเพียงสององค์ประกอบ 4 และ 6 ที่มีความถี่น้อยที่สุด ดังนั้นการนับเป็น 2

ป้อนข้อมูล −

linked list 1->1->2->2->2->3->3

ผลผลิต −

count is 2

คำอธิบาย −

ความถี่ต่ำสุดในตัวอย่างข้างต้นคือ 2 และมีองค์ประกอบสององค์ประกอบที่มีความถี่ต่ำสุดคือ 1 และ 3 ดังนั้นการนับคือ 2

ป้อนข้อมูล −

linked list = 1->2->3->2->4->2->5

ผลผลิต −

count is 4

คำอธิบาย −

ความถี่ต่ำสุดในตัวอย่างข้างต้นคือ 1 และมี 4 องค์ประกอบที่มีความถี่ต่ำสุดคือ 1, 3, 4 และ 5 ดังนั้นการนับคือ 4

แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้

• กำหนดรายการเชื่อมโยงและผลักดันองค์ประกอบในรายการที่เชื่อมโยง

• ในฟังก์ชันขั้นต่ำเพื่อค้นหาจำนวนองค์ประกอบที่มีความถี่ต่ำสุด ให้ประกาศแผนที่ "mymap" เพื่อเก็บความถี่ของตัวเลข

• สำรวจรายการและจัดเก็บความถี่ (การเกิดขึ้น) ขององค์ประกอบในแผนที่ของฉัน

• หลังจากที่เราพบความถี่และเก็บความถี่ใน mymap แล้ว ให้หาความถี่ต่ำสุด

• นับความถี่ จำนวนครั้งที่เกิดขึ้นใน mymap

• คืนค่าการนับ

ตัวอย่าง

#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;
struct Node {
   int key;
   struct Node* next;
};
// to push the values in the stack
void push(struct Node** head_ref, int new_key){
   struct Node* new_node = new Node;
   new_node->key = new_key;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
// Function to count minimum frequency elements
// in the linked list
int minimum(struct Node* head){
   // Store frequencies of all nodes.
   unordered_map<int, int> mymap;
   struct Node* current = head;
   while (current != NULL){
      int value = current->key;
      mymap[value]++;
      current = current->next;
   }
   // Find min frequency
   current = head;
   int min = INT_MAX, count = 0;
   for (auto it = mymap.begin(); it != mymap.end(); it++){
      if (it->second <= min){
         min = it->second;
      }
   }
   // Find count of min frequency elements
   for (auto it = mymap.begin(); it != mymap.end(); it++){
      if (it->second == min){
         count += (it->second);
      }
   }
   return count;
}
int main(){
   /* Starting with an empty list */
   struct Node* head = NULL;
   int x = 21;
   push(&head, 30);
   push(&head, 50);
   push(&head, 61);
   push(&head, 40);
   push(&head, 30);
   cout <<"count is: "<<minimum(head) << endl;
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -

count is: 3