주어진 작업은 중복 요소가 있는 주어진 연결 목록에서 최소 빈도 요소를 계산하는 것입니다.
연결 목록은 각 요소가 다음 요소에 연결된 목록처럼 데이터가 직렬 순서로 저장되는 데이터 구조입니다.
연결 목록에서 요소의 빈도는 연결 목록에서 요소가 발생하는 횟수를 나타냅니다. 문제에 따르면 연결 목록에서 최소 빈도를 계산해야 합니다.
연결 목록 1, 1, 3, 1, 3, 4, 6이 있다고 가정해 보겠습니다. 여기서 최소 주파수는 1이므로 최소 주파수를 갖는 요소를 계산해야 합니다. 빈도가 가장 낮은 두 개의 요소 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