数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律学从数组中移除最少元素以使 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
更新于：2019 年 12 月 23 日
295 次浏览
广告