C++에서 주어진 요소를 삭제한 후 k개의 가장 작은 숫자 찾기

이 문제에서는 크기가 n인 배열 arr[], 크기가 m인 배열 del[], 정수 k가 제공됩니다. 우리의 임무는 주어진 요소를 삭제한 후 가장 작은 k개를 찾는 것입니다. .

del[] 배열에 있는 모든 요소를 ​​삭제한 후 찾은 배열 arr[]에서 처음 k개의 가장 작은 요소를 인쇄해야 합니다. 배열에 두 개의 인스턴스가 있는 경우 첫 번째 인스턴스를 삭제합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

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