【C++】指定された要素を削除した後、配列からk個の最大値を見つける方法

問題の概要

この記事では、サイズnの整数型配列arr[]、サイズmの配列del[]、および整数kが与えられたときに、指定された要素を削除した後のk個の最大値を見つける方法を解説します。

具体的には、del[]に含まれるすべての要素をarr[]から削除し、残った配列の中から大きい方からk個の要素を出力します。なお、同じ値が複数存在する場合は、先に出現したインスタンスを削除するものとします。

例で理解しよう

入力 : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2
出力 : 7, 5

説明：

要素を削除した後の配列arr[] : {5, 7, 2}
最大の2要素は 7 と 5。

解法アプローチ①：ソートを使うシンプルな方法

最もシンプルな解決策は、まずarr[]からdel[]に存在するすべての要素を削除し、その後配列を降順にソートして、先頭のk個の要素を出力するというものです。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
void findKmaxElementDelArray(int arr[], int n, int del[], int m, int k){
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(arr[j] == del[i]){
                arr[j] = INT_MIN;
                break;
            }
        }
    }
    sort(arr, arr + n, greater<int>());
    for (int i = 0; i < k; ++i) {
        cout<<arr[i]<<" ";
    }
}
int main(){
   int array[] = { 3, 5, 1, 7, 9, 2 };
   int m = sizeof(array) / sizeof(array[0]);
   int del[] = { 1, 9, 3 };
   int n = sizeof(del) / sizeof(del[0]);
   int k = 2;
   cout<<k<<" largest numbers after deleting the elements are ";
   findKmaxElementDelArray(array, m, del, n, k);
   return 0;
}

出力結果

2 largest numbers after deleting the elements are 7 5

解法アプローチ②：ハッシュマップとヒープを使う方法

もうひとつのアプローチとして、ハッシュマップ（unordered_map）とヒープ（priority_queue）を組み合わせる方法があります。まず最大ヒープとハッシュマップを作成し、ハッシュマップにはdel[]配列のすべての要素を格納します。次に、ハッシュマップに存在しないarr[]の要素だけを最大ヒープに挿入します。最後に、ヒープからk個の要素を取り出して出力すれば完成です。

この方法では、削除対象の要素を実際に配列から取り除く代わりに、ハッシュマップによる照合で該当要素をスキップできるため、大規模なデータを扱う場合により効率的に処理できます。

実装例

#include <bits/stdc++.h>
using namespace std;
void findKmaxElementDelArray(int arr[], int n, int del[], int m, int k){
    unordered_map<int, int> deleteElement;
    for (int i = 0; i < m; ++i) {
        deleteElement[del[i]]++;
    }
    priority_queue<int> maxHeap;
    for (int i = 0; i < n; ++i) {
        if (deleteElement.find(arr[i]) != deleteElement.end()) {
            deleteElement[arr[i]]--;
            if (deleteElement[arr[i]] == 0) deleteElement.erase(arr[i]);
        }
        else
            maxHeap.push(arr[i]);
    }
    for (int i = 0; i < k; ++i) {
        cout<<maxHeap.top()<<" ";
        maxHeap.pop();
    }
}
int main(){
   int array[] = { 3, 5, 1, 7, 9, 2 };
   int m = sizeof(array) / sizeof(array[0]);
   int del[] = { 1, 9, 3 };
   int n = sizeof(del) / sizeof(del[0]);
   int k = 2;
   cout<<k<<" largest numbers after deleting the elements are ";
   findKmaxElementDelArray(array, m, del, n, k);
   return 0;
}

出力結果

2 largest numbers after deleting the elements are 7 5

まとめ

指定された要素を削除した後のk個の最大値を求める問題に対して、①削除後に降順ソートを行うシンプルな手法と、②ハッシュマップと最大ヒープを活用する効率的な手法の2つを紹介しました。データ量が多く、かつkが小さい場合は、ヒープを使ったアプローチの方が計算コストを抑えられる点で有利です。用途に応じて最適な方法を選択しましょう。