Đếm phần tử tần số tối thiểu trong danh sách liên kết trong C ++

Nhiệm vụ được giao là đếm các phần tử tần suất tối thiểu trong một danh sách được liên kết nhất định có các phần tử trùng lặp.

Danh sách được liên kết là một cấu trúc dữ liệu trong đó dữ liệu được lưu trữ theo thứ tự nối tiếp, giống như một danh sách mà mỗi phần tử được liên kết với phần tử tiếp theo.

Tần suất của một phần tử trong danh sách được liên kết đề cập đến số lần một phần tử xuất hiện trong danh sách được liên kết. Theo vấn đề, chúng tôi phải đếm tần suất tối thiểu trong danh sách được liên kết.

Giả sử chúng ta có một danh sách liên kết, 1, 1, 3, 1, 3, 4, 6; trong đó tần số tối thiểu là một vì vậy chúng ta phải đếm các phần tử, những phần tử đang có tần số tối thiểu. Chỉ có hai phần tử 4 và 6 có tần số ít nhất nên số lượng là 2.

Đầu vào -

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

Đầu ra -

count is 2

Giải thích -

Tần số tối thiểu trong ví dụ trên là 2 và có hai phần tử có tần số nhỏ nhất, tức là 1 và 3, vì vậy số đếm là 2.

Đầu vào -

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

Đầu ra -

count is 4

Giải thích -

Tần số tối thiểu trong ví dụ trên là 1 và có 4 phần tử có tần số nhỏ nhất, tức là 1, 3, 4 và 5, vì vậy số lượng là 4.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Xác định danh sách được liên kết và đẩy các phần tử trong danh sách được liên kết.

• Trong hàm tối thiểu để tìm số lượng các phần tử có tần suất nhỏ nhất, hãy khai báo bản đồ “mymap” để lưu trữ tần số của các số.

• Duyệt qua danh sách và lưu trữ tần suất (sự xuất hiện) của các phần tử trong bản đồ của tôi.

• Sau khi chúng tôi tìm thấy các tần số và lưu trữ các tần số trong bản đồ của tôi, sau đó tìm tần số tối thiểu.

• Đếm số lần tần suất đã xảy ra trong bản đồ của tôi.

• Trả lại số đếm.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -

count is: 3