C++で指定した要素を削除した後にk個の最小値を見つける方法

問題の概要

この問題では、サイズnの配列arr[]、サイズmの配列del[]、そして整数kが与えられます。求められているのは、指定された要素を削除した後にk個の最小値を見つけることです。

具体的には、配列arr[]からdel[]に含まれるすべての要素を削除した後の、小さい方からk個の要素を出力する必要があります。同じ値が複数存在する場合は、最初に出現したインスタンスを削除するものとします。

例を使って問題を理解しましょう。

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

説明 −

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

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

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

削除処理にはO(m×n)、ソートにはO(n log n)の時間がかかるため、全体の計算量はO(n log n + m×n)となります。

実装例

この解決策の動作を示すプログラムです。

#include <bits/stdc++.h>
using namespace std;
void findKminElementDelArray(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_MAX;
            break;
         }
      }
   }
   sort(arr, arr + n);
   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<<" smallest numbers after deleting the elements are ";
   findKminElementDelArray(array, m, del, n, k);
   return 0;
}

出力

2 smallest numbers after deleting the elements are 2 5

削除対象の要素が見つかった場合、その値をINT_MAXに置き換えることで実質的に削除しています。その後ソートを行うことで、INT_MAXの要素は配列の末尾に移動するため、先頭のk個が求める最小値となります。

解決アプローチ2：ハッシュマップと最小ヒープを使う効率的な方法

より効率的なアプローチとして、ハッシュマップと最小ヒープ（min-heap）を組み合わせる方法があります。

手順は以下の通りです。

1. ハッシュマップを作成し、配列del[]のすべての要素を登録します。
2. 配列arr[]の要素を順に走査し、ハッシュマップに存在しない要素だけを最小ヒープに挿入します。
3. ヒープからk個の要素を取り出して出力します。

この方法では、削除対象の要素をハッシュマップでO(1)で判定できるため、削除処理がO(n + m)で完了し、全体の計算量はO(n + m + k log n)と大幅に改善されます。

実装例

この解決策の動作を示すプログラムです。

#include <bits/stdc++.h>
using namespace std;
void findKminElementDelArray(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, vector<int>, greater<int> > minHeap;
   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
         minHeap.push(arr[i]);
   }
   for (int i = 0; i < k; ++i) {
      cout<<minHeap.top()<<" ";
      minHeap.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<<" smallest numbers after deleting the elements are ";
   findKminElementDelArray(array, m, del, n, k);
   return 0;
}

出力

2 smallest numbers after deleting the elements are 2 5

まとめ

配列から指定した要素を削除した後にk個の最小値を求める問題には、主に2つのアプローチがあります。

データサイズが小さい場合はシンプルなソートベースの方法で十分ですが、配列が大きい場合やパフォーマンスが重要な場面では、ハッシュマップと最小ヒープを組み合わせた方法が効率的です。del[]に同じ値が複数含まれるケースにも対応できるよう、ハッシュマップで出現回数を管理している点がポイントです。