毎日のアルゴリズム: 上位 K 個の高頻度要素

空でない整数の配列が与えられた場合、最も頻繁に出現する上位 k 個の要素を返します。

例1:

入力: nums = [1,1,1,2,2,3]、k = 2
出力: [1,2]

例2:

入力: nums = [1]、k = 1
出力: [1]

ヒント：

与えられた k は常に妥当であり、1 ≤ k ≤ 配列内の一意の要素の数であると想定できます。
アルゴリズムの時間計算量は O(nlogn) より小さくなければなりません。ここで n は配列のサイズです。
質問データは、回答が一意であることを保証します。つまり、配列の最初の k 個の高頻度要素のセットは一意です。
回答は任意の順序で返すことができます。

解決策1: マップ+配列

マップを使用して各要素の頻度を記録し、配列を使用して要素を比較および並べ替えます。

コード実装:

 topKFrequent =関数(nums, k) {
    map = new Map(), arr = [...新しいSet (nums)] とします。
    nums.map((num) => {
        map.has(num) の場合、 map.set (num, map.get(num)+1) を実行します。
それ以外の場合は、 map.set (num, 1)
    })
 arr.sort((a, b) => map.get(b) - map.get(a)).slice(0, k);を返します。
 };

複雑性分析:

時間計算量: O(nlogn)
空間計算量: O(n)

質問では、アルゴリズムの時間計算量が O(n log n) より優れている必要があるため、この実装は質問の要件を満たしていません。

解決策 2: マップ + 小さなトップヒープ

配列を走査して各要素の頻度をカウントし、要素の値（キー）と出現頻度（値）をマップに保存します。

マップデータを通じて、上位 k 個の高頻度要素の小さなトップヒープが構築されます。小さなトップヒープ上の任意のノードの値は、その左と右の子ノードの値以下である必要があります。つまり、ヒープの上部が最小値です。

具体的な手順は次のとおりです。

データを走査し、各要素の頻度をカウントし、要素の値（キー）と出現頻度（値）をマップに保存します。
マップを横断し、最初のk個の数字で小さなトップヒープを構築します。
位置 k から始めて、マップのトラバースを続けます。各データの発生頻度は、小さなトップヒープの最上位要素の発生頻度と比較されます。最上位要素より小さい場合は、処理は行われず、次の要素へのトラバースが続行されます。最上位要素より大きい場合は、この要素がヒープの最上位要素を置き換え、ヒープが小さなトップヒープに変換されます。
トラバーサルが完了すると、ヒープ内のデータは上位k個の最大データになります。

コード実装:

 topKFrequent =関数(nums, k) {
    map = new Map()、heap = [,] とします。
    nums.map((num) => {
        map.has(num) の場合、 map.set (num, map.get(num)+1) を実行します。
それ以外の場合は、 map.set (num, 1)
    })
    // 要素数がk以下の場合
    マップのサイズがk以下の場合
[...map.keys()]を返す
    }
    // 要素数が k より大きい場合は、マップをトラバースして小さなトップヒープを構築します
    i = 0とする
    map.forEach((値、キー) => {
        i < k の場合 {
            // 最初の k を取得してヒープを構築し、それをヒープに挿入します
            heap.push(キー)
            // 最初の k 個のヒープをその場で作成します
            if(i === k-1) ヒープを構築(ヒープ、マップ、k)
        }そうでない場合、map.get(heap[1]) < 値) {
            // 置き換えてスタックする
            ヒープ[1] =キー
            // 最初の要素を上から下に積み重ねる
            ヒープ化(ヒープ, マップ, k, 1)
        }
        私は++
    })
    // ヒープの最初の要素を削除します
    ヒープ.shift()
ヒープを返す
};
 // 後ろから前へ、上から下へ、その場でヒープを構築します
buildHeap = (ヒープ、マップ、k) => {
    if(k === 1)戻り値
    // 最後の非リーフノードから始めて上から下に積み重ねます
(i = Math.floor(k/2); i>=1; i --)の場合{
        ヒープ化(ヒープ, マップ, k, i)
    }
 }
 // ヒープ
ヒープ化 = (ヒープ、マップ、k、i) => {
    // トップダウンスタッキング
    while( true ) {
        minIndex = i とします
        2*i <= k && map.get(heap[2*i]) < map.get(heap[i])) {
            最小インデックス = 2*i
        }
        if(2*i+1 <= k && map.get(heap[2*i+1]) < map.get(heap[minIndex])) {
            最小インデックス = 2*i+1
        }
        最小インデックスが i の場合
            swap(ヒープ, i, minIndex)
            i = 最小インデックス
        }それ以外{
            壊す
        }
    }
 }
 // 交換
swap = (arr, i, j) => {とします。
    temp = arr[i]とします。
    arr[i] = arr[j]
    arr[j] =一時
}

複雑性分析:

時間計算量: 配列の走査には O(n) の時間計算量が必要で、ヒープ化には O(logk) の時間計算量が必要であるため、ヒープを使用して Top k 問題を見つける時間計算量は O(nlogk) です。
空間計算量: O(n)

解決策3: バケットソート

ここでは、最初のk個の高頻度要素を取得する必要があり、カウンティングソートはもはや適していません。前の質問では、カウンティングソートを使用して、要素iがbucket[i]に出現した回数を保存しましたが、この保存ではバケット配列上の値が順番になっていることを保証できません。たとえば、bucket = [0,3,1,2]、つまり要素0は出現せず、要素1は3回出現し、要素2は1回出現し、要素3は2回出現します。したがって、カウンティングソートは最初のk個の高頻度要素を取得するのに適していません。ただし、カウンティングソートが機能しない場合は、バケットソートがあるので心配しないでください。

バケットソートは、カウントソートのアップグレード版です。また、関数のマッピング関係も活用します。

バケットソートは、入力データが均一に分散されていると想定し、データを有限数のバケットに分割し、各バケットを個別にソートすることによって機能します (別のソートアルゴリズムを使用することも、バケットソートを再帰的に使用し続けることもできます)。

まずマップを使用して頻度を保存します
次に、配列（特定の数のバケットを持つ）を作成し、頻度を配列の添え字として使用して、異なる頻度を持つ数値セットを対応する配列の添え字（バケット内）に格納します。

コード実装:

 topKFrequent =関数(nums, k) {
    map = new Map(), arr = [...新しいSet (nums)] とします。
    nums.map((num) => {
        map.has(num) の場合、 map.set (num, map.get(num)+1) を実行します。
それ以外の場合は、 map.set (num, 1)
    })
    // 要素数がk以下の場合
    マップのサイズがk以下の場合
[...map.keys()]を返す
    }
バケットソート(map, k)を返す
};
 // バケットソート
バケットソート = (map, k) => {
    arr = []、res = []とします。
    map.forEach((値、キー) => {
        // マッピング関係（出現頻度を添え字とする）を使用して、各バケットにデータを分配します
        if(!arr[値]) {
            arr[値] = [キー]
        }それ以外{
            arr[値].push(キー)
        }
    })
    // 逆順に走査して、最も頻度の高い最初の k 個の数値を取得します。
 (i = arr.length - 1;i >= 0 && res.length < k;i --) {
        if(arr[i]) {
            res.push(...arr[i])
        }
 }
戻り値
}