在C ++中从数组中移除的最小值最小，以使max – min <= K
问题陈述
给定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. Sort the given elements 2. Using greedy approach, the best way is to remove the minimum element or the maximum element and then check if Amax - Amin <= K. There are various combinations of removals that have to be considered. 3. There will be two possible ways of removal, either we remove the minimum or we remove the maximum. Let(i…j) be the index of elements left after removal of elements. Initially, we start with i=0 and j=n-1 and the number of elements removed is 0 at the beginnings. 4. We only remove an element if a[j]-a[i]>k, the two possible ways of removal are (i+1…j) or (i…j-1). The minimum of the two is considered
示例
#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
热门推荐
10 圣诞祝福语简短小学
11 祖国七十华诞简短祝福语
12 老师送的祝福语简短
13 生日祝福语大全女生简短
14 祝女性生日祝福语简短
15 牛年女神节祝福语简短
16 情人表白祝福语简短大气
17 老公开业祝福语简短
18 官宣新年祝福语简短