Cho nhiệm vụ là đếm các phần tử có tần suất tối thiểu trong một danh sách liên kết đã cho chứa các phần tử trùng lặp.
Danh sách 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, như một danh sách, 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 liên kết là số lần phần tử đó xuất hiện trong danh sách. Theo bài toán, chúng ta phải đếm số phần tử có tần suất nhỏ nhất trong danh sách 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; tần suất nhỏ nhất là 1 nên chúng ta phải đếm các phần tử có tần suất nhỏ nhất. Chỉ có hai phần tử 4 và 6 với tần suất nhỏ nhất nên đếm là 2.
Đầu vào −
danh sách liên kết 1->1->2->2->2->3->3
Đầu ra −
đếm là 2
Giải thích −
Tần suất nhỏ nhất trong ví dụ trên là 2 và có hai phần tử với tần suất nhỏ nhất là 1 và 3, nên đếm là 2.
Đầu vào −
danh sách liên kết = 1->2->3->2->4->2->5
Đầu ra −
đếm là 4
Giải thích −
Tần suất nhỏ nhất trong ví dụ trên là 1 và có 4 phần tử với tần suất nhỏ nhất là 1, 3, 4, và 5, nên đếm là 4.
Phương pháp sử dụng trong chương trình dưới đây như sau
Định nghĩa một danh sách liên kết và đẩy các phần tử vào danh sách.
Trong hàm minimum để tìm số phần tử có tần suất nhỏ nhất, khai báo một map "mymap" để lưu tần suất của các số.
Duyệt danh sách và lưu tần suất (số lần xuất hiện) của các phần tử vào mymap.
Sau khi tìm thấy tần suất và lưu vào mymap, tìm tần suất nhỏ nhất.
Đếm số lần tần suất đó xuất hiện trong mymap.
Trả về đếm.
Ví dụ
#include <iostream> #include <unordered_map> #include <climits> using namespace std; struct Node { int key; struct Node* next; }; // để đẩy giá trị vào 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){ // Lưu tần suất của tất cả các node. unordered_map<int, int> mymap; struct Node* current = head; while (current != NULL){ int value = current->key; mymap[value]++; current = current->next; } // Tìm tần suất nhỏ nhất current = head; int min = INT_MAX, count = 0; for (auto it = mymap.begin(); it != mymap.end(); it++){ if (it->second <= min){ min = it->second; } } // Tìm số lượng phần tử có tần suất nhỏ nhất for (auto it = mymap.begin(); it != mymap.end(); it++){ if (it->second == min){ count += (it->second); } } return count; } int main(){ /* Bắt đầu với danh sách rỗng */ 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 mã trên, chúng ta sẽ nhận được đầu ra sau −
count is: 3