C++程式，用於從陣列兩端移除最少的元素，使得2倍最小值大於最大值

問題涉及從整數列表的兩端移除元素，使得2倍最小值大於最大值。

vector<int> arr = {250, 10, 11, 12, 19, 200};
res = solve(arr);

我們可以使用暴力搜尋的方法。我們可以嘗試所有滿足條件的子陣列，並找到其中2*min > max 條件成立的最長子陣列。我們也可以使用動態規劃方法來嘗試所有可能的子陣列組合，但這過於複雜且沒有必要。

示例（使用向量ADT）

假設我們有一個數組，例如“[250, 10, 11, 12, 19, 200]”。為了獲得最優解，我們需要移除元素[250, 200]，使陣列變為[10, 11, 12, 19]，其中最小值為10，最大值為19。所以2*10 > 19。我們從陣列中移除了2個元素，因此輸出列印為2。

以下是一個C++程式，演示瞭如何從陣列中移除最少的元素，使得最小值的2倍大於最大值：

#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

示例（不使用向量ADT）

以下是一個C++程式，演示瞭如何從陣列中移除最少的元素，使得最小值的2倍大於最大值，但不使用向量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)，因為我們遍歷了所有子陣列。

更新於：2022年8月10日

320次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

立即開始
廣告