C++で連結リスト内の最小頻度要素をカウントする方法

はじめに

本記事では、重複する要素を含む連結リスト（リンクリスト）が与えられたときに、最小頻度の要素をカウントする方法について解説します。

連結リストとは、データを順番に格納するデータ構造の一種で、リストのように各要素が次の要素へと順次連結された形をしています。

連結リストにおける要素の出現頻度とは、その要素がリスト内に出現する回数のことを指します。今回の問題では、連結リスト内で最も出現回数が少ない頻度（最小頻度）を求め、それに該当する要素をカウントする必要があります。

例えば、1, 1, 3, 1, 3, 4, 6 という連結リストを考えてみましょう。この場合、最小頻度は1であるため、最小頻度を持つ要素を数える必要があります。最も出現回数が少ないのは 4 と 6 の2つの要素だけなので、カウントは 2 となります。

入力・出力の例

例1

入力：

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

出力：

count is 2

説明：
上記の例では、最小頻度は2であり、その頻度を持つ要素は 1 と 3 の2つです。したがって、カウントは2となります。

例2

入力：

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

出力：

count is 4

説明：
上記の例では、最小頻度は1であり、その頻度を持つ要素は 1、3、4、5 の4つです。したがって、カウントは4となります。

プログラムのアプローチ

以下のプログラムでは、次の手順で問題を解いています。

• 連結リストを定義し、要素をリストに追加（push）します。
• 最小頻度の要素数を求める minimum 関数内で、数値の出現頻度を格納するためのマップ mymap を宣言します。
• リストを走査しながら、各要素の出現頻度を mymap に格納していきます。
• すべての頻度を mymap に格納した後、最小の頻度値を求めます。
• mymap 内で最小頻度に一致する要素について、その出現回数を合計してカウントします。
• 最終的なカウントを返します。

サンプルコード

#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;
struct Node {
    int key;
    struct Node* next;
};
// 値をリストに追加する関数
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;
}
// 連結リスト内の最小頻度要素を
// カウントする関数
int minimum(struct Node* head){
    // すべてのノードの頻度を格納
    unordered_map<int, int> mymap;
    struct Node* current = head;
    while (current != NULL){
        int value = current->key;
        mymap[value]++;
        current = current->next;
    }
    // 最小頻度を求める
    current = head;
    int min = INT_MAX, count = 0;
    for (auto it = mymap.begin(); it != mymap.end(); it++){
        if (it->second <= min){
            min = it->second;
        }
    }
    // 最小頻度要素の個数を数える
    for (auto it = mymap.begin(); it != mymap.end(); it++){
        if (it->second == min){
            count += (it->second);
        }
    }
    return count;
}
int main(){
    /* 空のリストから開始 */
    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

まとめ

このように、unordered_map を活用することで、連結リスト内の各要素の出現頻度を効率的に記録できます。計算量はリストの走査にO(n)、マップの操作にO(1)程度となるため、大きなデータセットに対しても高速に動作します。最小頻度の要素を特定したい場面では、ぜひこの手法を活用してみてください。