Mô tả bài toán
Cho mảng arr[] và mảng del[]. Xóa khỏi arr tất cả các giá trị xuất hiện trong del (mỗi giá trị trong del xóa một lần xuất hiện tương ứng). Tìm giá trị nhỏ nhất còn lại.
Ví dụ
arr = {2,5,6,9,1}, del = {1,5,9} → Output: 2.
Giải thuật
Sử dụng unordered_map đếm tần suất các giá trị trong del. Duyệt arr: nếu giá trị có trong map thì giảm đếm (xóa khỏi map khi đếm về 0), else cập nhật minVal.
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
int findSmallestVal(int arr[], int m, int del[], int n) {
unordered_map<int,int> delVals;
for (int i=0; i<n; ++i) delVals[del[i]]++;
int minVal = INT_MAX;
for (int i=0; i<m; ++i) {
if (delVals.find(arr[i]) != delVals.end()) {
delVals[arr[i]]--;
if (delVals[arr[i]] == 0) delVals.erase(arr[i]);
} else minVal = min(minVal, arr[i]);
}
return minVal;
}
int main() {
int array[] = {5,12,33,4,56,12,20};
int m = sizeof(array)/sizeof(array[0]);
int del[] = {12,4,56,5};
int n = sizeof(del)/sizeof(del[0]);
cout << "The smallest value after deleting elements is " << findSmallestVal(array,m,del,n);
return 0;
}Đầu ra
The smallest value after the deleting element is 12