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 次浏览

启动您的职业生涯

完成课程后获得认证

开始
广告