C++程式：替換元素使陣列元素連續

給定一個元素陣列，我們需要確定是否可以透過更改任何一個元素的值來使陣列元素連續。如果不可能，則返回 -1；否則，返回需要更改的元素。

假設我們有一個數組 {4, 3, 9, 5, 6}，我們需要對這個陣列進行排序。然後從最小和最大元素開始，檢查不匹配的個數。如果陣列兩側的不匹配個數都超過 1，則答案為 -1。否則，可以找到需要更改的元素。

演算法（步驟）

以下是執行所需任務的演算法/步驟：

  • 以陣列（輸入陣列）的形式獲取所需的值。

  • 一系列連續的元素從陣列的最小元素開始，透過將 1 加到前一個元素來繼續。

  • 一系列連續的元素從陣列的最大元素開始，然後透過從前一個元素中減去 1 來繼續。

  • 建立上面提到的兩個序列，然後在陣列中查詢每個序列的元素。如果兩個序列之間存在多個不匹配，則不可能。如果在任何序列中可以檢測到一個不匹配，我們就有答案了。

示例

下面實現一個 C++ 程式，該程式替換陣列元素，以便所有陣列元素都成為連續的：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solve(vector<int> arr) {
   sort(arr.begin(), arr.end());
   int n = arr.size();
   int mismatch = 0, ans;
   int nextElement = arr[n-1] - n + 1;
   for (int i=0; i<n-1; i++, nextElement++) {
      if (binary_search(arr.begin(), arr.end(), nextElement) == 0) {
         ans = arr[0];
         mismatch++;
      }
   }
   if (mismatch == 1)
      return ans;
   if (mismatch == 0)
      return 0;
   mismatch = 0;
   nextElement = arr[0] + n - 1;
   for (int i=n-1;i>=1;i--, nextElement--) {
      if (binary_search(arr.begin(), arr.end(), nextElement) == 0) {
         ans = arr[n-1];
         mismatch++;
      }
   }
   if (mismatch == 1)
      return ans;
   return -1;
}
int main() {
   vector<int> arr = {4, 3, 9, 5, 6};
   int ans = solve(arr);
   if (ans == -1)
      cout << "Impossible";
   else if (ans == 0)
      cout << "Already consecutive";
   else
      cout << ans;
   return 0;
}

將元素 9 更改為 2 或 7 將使整組元素連續。陣列變為 = {4, 3, 7, 5, 6}，輸出將為：

輸出

9

結論

該演算法的時間複雜度為 O(nlog(n))。我們還可以使用不同的陣列來解決此確切問題，並查詢陣列中差異變化的位置是否超過一個，以及更多方法。在瞭解了這種基本方法之後，您可以嘗試一下。

更新於：2022年8月10日

488 次瀏覽

啟動您的職業生涯

完成課程後獲得認證

開始
廣告
© . All rights reserved.