C ++で特定の要素を削除した後、k個の最小数を見つけます

この問題では、サイズnの配列arr []、サイズmの配列del []、および整数kが与えられます。私たちのタスクは、指定された要素を削除した後にk個の最小数を見つけることです。 。

del[]配列に存在するすべての要素を削除した後に見つかった配列arr[]から最初のk個の最小要素を出力する必要があります。アレイに2つのインスタンスが存在する場合は、最初のインスタンスを削除します。

問題を理解するために例を見てみましょう

Input : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2
Output : 2, 5

説明 −

Array arr[] after deleting the elements : {5, 7, 2}
2 minimum elements are 2, 5.

ソリューションアプローチ

問題の簡単な解決策は、del[]に存在するarr[]からすべての要素を削除することです。次に、配列を昇順で並べ替え、配列の最初のk個の要素を出力します。

例

ソリューションの動作を説明するプログラム

#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

別のアプローチ

この問題を解決する別のアプローチは、ハッシュマップとヒープを使用することです。最小ヒープとハッシュマップを作成します。ハッシュマップには、配列del[]のすべての要素が含まれます。次に、ハッシュマップに存在しない配列arr[]の要素を最小ヒープに挿入します。ヒープからk個の要素をポップして、それを印刷します。

例

ソリューションの動作を説明するプログラム

#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