C++ 中如何从数组中移除最少元素，使最大值 – 最小值 <= K
c++server side programmingprogramming
问题描述
给定 N 个整数和 K 个元素，求出需要移除的最小元素数，使得 Amax - Amin <= K。移除元素后，剩余元素中将包含 Amax 和 Amin。
示例
如果 arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20} 且 k = 4，则输出为 5:
- 从数组开头移除 1、3 和 4
- 从数组末尾移除 17 和 20
- 最终数组变为 {9, 10, 11, 12}，其中 12 – 9 <= 4
算法
1. 对给定元素进行排序 2. 使用贪婪算法，最佳方法是移除最小元素或最大元素，然后检查 Amax - Amin 是否 <= K。移除元素的组合有很多种，需要考虑。 3. 移除元素有两种可能的方式:移除最小元素或移除最大元素。令 (i…j) 为移除元素后剩余元素的索引。初始时 i=0，j=n-1，移除元素个数为 0。 4. 仅当 a[j]-a[i]>k 时才移除元素，两种可能的移除方式是 (i+1…j) 或 (i…j-1)。取两者中较小的一个。
示例
#include <bits/stdc++.h>
#define MAX 100
using namespace std;
int dp[MAX][MAX];
int removeCombinations(int *arr, int i, int j, int k) {
if (i >= j) {
return 0;
} else if ((arr[j] - arr[i]) <= k) {
return 0;
} else if (dp[i][j] != -1) {
return dp[i][j];
} else if ((arr[j] - arr[i]) > k) {
dp[i][j] = 1 + min(removeCombinations(arr, i +
1, j, k),
removeCombinations(arr, i, j - 1,k));
}
return dp[i][j];
}
int removeNumbers(int *arr, int n, int k){
sort(arr, arr + n);
memset(dp, -1, sizeof(dp));
return n == 1 ? 0 : removeCombinations(arr, 0, n - 1,k);
}
int main() {
int arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
cout << "Minimum numbers to be removed = " <<
removeNumbers(arr, n, k) << endl;
return 0;
}
编译并执行上述程序，将生成以下输出
输出
Minimum numbers to be removed = 5
