資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告