該問題涉及以 2*min 大於 max 的方式從整數列表的任意一側刪除元素。
vector<int> arr = {250, 10, 11, 12, 19, 200};
res = solve(arr);
我們可以使用暴力方法。我們可以嘗試所有可能的滿足並找到滿足 2*min > max 條件的最長子數組。我們也可以使用動態規劃方法來嘗試所有可能的過度且不必要的子陣列組合。
假設我們有一個數組，例如「[250, 10, 11, 12, 19, 200]」。為了獲得最佳解決方案，我們需要刪除元素 [250, 200] 以形成陣列 [10, 11, 12, 19]，其中 min 為 10，max 為 19。因此 2*10 > 19。我們從數組，因此輸出列印為 2。
下面是一個 C 程序，它描述瞭如何從數組中刪除最小數量的元素，使得最小值的兩倍大於最大值 -
#include <iostream>
#include <vector>
using namespace std;
int solve(vector<int> arr) {
int startIndex = 0, endIndex = 0;
bool foundAnAnswer = false;
for (int start=0; start<arr.size(); start++) {
int min = INT32_MAX, max = INT32_MIN;
for (int end=start; end<arr.size(); end++) {
if (arr[end] < min) min = arr[end];
if (arr[end] > max) max = arr[end];
if (2*min <= max) break;
if (end - start > endIndex - startIndex || !foundAnAnswer) {
startIndex = start;
endIndex = end;
foundAnAnswer = true;
}
}
}
if (!foundAnAnswer) return arr.size();
return (arr.size() - (endIndex - startIndex + 1));
}
int main() {
vector<int> arr = {250, 10, 11, 12, 19, 200};
cout << solve(arr);
return 0;
}
2
下面是一個 C 程序，描述如何從數組中刪除最小數量的元素，使得最小值的兩倍大於最大值，但不使用 Vector ADT -
#include <iostream>
using namespace std;
int min(int a, int b) {return (a < b)? a : b;}
int min(int arr[], int low, int high)
{
int minimum = arr[low];
for (int i=low+1; i<=high; i++)
if (minimum > arr[i])
minimum = arr[i];
return minimum;
}
int max(int arr[], int low, int high)
{
int maximum = arr[low];
for (int i=low+1; i<=high; i++)
if (maximum < arr[i])
maximum = arr[i];
return maximum;
}
int minimum_removals(int arr[], int low, int high)
{
if (low >= high)
return 0;
int m1 = min(arr, low, high);
int m2 = max(arr, low, high);
if (2*m1 > m2)
return 0;
return min(minimum_removals(arr, low+1, high), minimum_removals(arr, low, high-1)) + 1;
}
int main()
{
int arr[] = {12, 45, 32, 88, 100};
int n = sizeof(arr)/sizeof(arr[0]);
cout << minimum_removals(arr, 0, n-1);
return 0;
}
3
這裡我們使用暴力方法來找出最長的子陣列。其他可能的解決方案可能包括透過重複從兩側彈出元素以及其他方法來檢查每個可能的子陣列。儘管如此，它們的實施工作量很大，而且優化程度較低。這裡的時間複雜度是 O(n^2)，因為我們已經遍歷了所有子陣列。
以上是C++程序，從兩邊刪除最小的元素，使得2*最小值大於最大值的詳細內容。更多資訊請關注PHP中文網其他相關文章！
