# 替換元素會使數組元素連續 > 原文： [https://www.geeksforgeeks.org/replacing-an-element-makes-array-elements-consecutive/](https://www.geeksforgeeks.org/replacing-an-element-makes-array-elements-consecutive/) 給定正整數的數組。 我們需要找到唯一的元素，其任何其他值的替換都會使數組元素變得連續不同。 如果不可能使數組元素連續，則返回-1。 **示例**： ``` Input : arr[] = {45, 42, 46, 48, 47} Output : 42 Explanation: We can replace 42 with either 44 or 48 to make array consecutive. Input : arr[] = {5, 6, 7, 9, 10} Output : 5 [OR 10] Explanation: We can either replace 5 with 8 or 10 with 8 to make array elements consecutive. Input : arr[] = {5, 6, 7, 9, 8} Output : Array elements are already consecutive ``` **樸素的方法**是要檢查 arr []的每個元素，在替換后使[連續或不連續](https://www.geeksforgeeks.org/check-array-elements-consecutive-time-o1-space-handles-positive-negative-numbers/)。 此方法的時間復雜度 `O(n^2)` **更好的方法**基于以下重要觀察結果：如果存在答案，則最小或最大元素將為答案。 如果存在答案，則有兩種情況。 1）一系列連續元素從數組的最小元素開始，然后通過在前一個元素上加 1 繼續。 2）一系列連續元素從數組的最大元素開始，然后從上一個元素中減去 1 繼續。 我們制作兩個以上的系列，對于每個系列，我們都在數組中搜索系列元素。 如果兩個系列的不匹配數均大于 1，則不存在答案。 如果發現任何一個序列不匹配，那么我們有答案。 ## C++ ```cpp // CPP program to find an element replacement // of which makes the array elements consecutive. #include <bits/stdc++.h> using namespace std; int findElement(int arr[], int n) { ????sort(arr, arr+n); ????// Making a series starting from first element ????// and adding 1 to every element.???? ????int mismatch_count1 = 0, res; ????int next_element = arr[n-1] - n + 1; ????for (int i=0; i<n-1; i++) { ???????if (binary_search(arr, arr+n, next_element) == 0) ???????{ ??????????res = arr[0];?? ??????????mismatch_count1++; ???????} ????????next_element++; ????}??? ????// If only one mismatch is found. ????if (mismatch_count1 == 1) ????????return res; ????// If no mismatch found, elements are ????// already consecutive. ????if (mismatch_count1 == 0)?? ????????return 0; ????// Making a series starting from last element ????// and subtracting 1 to every element.? ????int mismatch_count2 = 0; ????next_element = arr[0] + n - 1; ????for (int i=n-1; i>=1; i--) { ???????if (binary_search(arr, arr+n, next_element) == 0) ???????{ ??????????res = arr[n-1];?? ??????????mismatch_count2++; ???????}?????? ???????next_element--; ????} ????// If only one mismatch is found. ????if (mismatch_count2 == 1) ??????return res; ????return -1;?? } // Driver code int main() { ????int arr[] =? {7, 5, 12, 8} ; ????int n = sizeof(arr)/sizeof(arr[0]); ????int res = findElement(arr,n); ????if (res == -1) ??????cout << "Answer does not exist"; ????else if (res == 0) ??????cout << "Elements are already consecutive"; ????else ??????cout << res; ????return 0; } ``` ## Java ```java // Java program to find an element? // replacement of which makes? // the array elements consecutive. import java.io.*; import java.util.Arrays; class GFG { ????static int findElement(int []arr,? ???????????????????????????int n) ????{ ????????Arrays.sort(arr); ????????// Making a series starting? ????????// from first element and? ????????// adding 1 to every element.? ????????int mismatch_count1 = 0,? ????????????????????????res = 0; ????????int next_element = arr[n - 1] -? ???????????????????????????????n + 1; ????????for (int i = 0; i < n - 1; i++)? ????????{ ????????if (Arrays.binarySearch(arr,? ????????????????????????????next_element) < 0) ????????{ ????????????res = arr[0];? ????????????mismatch_count1++; ????????} ????????????next_element++; ????????}? ????????// If only one mismatch is found. ????????if (mismatch_count1 == 1) ????????????return res; ????????// If no mismatch found, elements? ????????// are already consecutive. ????????if (mismatch_count1 == 0)? ????????????return 0; ????????// Making a series starting ????????// from last element and? ????????// subtracting 1 to every element.? ????????int mismatch_count2 = 0; ????????next_element = arr[0] + n - 1; ????????for (int i = n - 1; i >= 1; i--)? ????????{ ????????if (Arrays.binarySearch(arr,? ????????????????????????????next_element) < 0) ????????{ ????????????res = arr[n - 1];? ????????????mismatch_count2++; ????????}????? ????????next_element--; ????????} ????????// If only one mismatch is found. ????????if (mismatch_count2 == 1) ????????return res; ????????return -1;? ????} ????// Driver code ????public static void main(String args[]) ????{ ????????int []arr = new int[]{7, 5, 12, 8} ; ????????int n = arr.length; ????????int res = findElement(arr,n); ????????if (res == -1) ????????System.out.print("Answer does not exist"); ????????else if (res == 0) ????????System.out.print("Elements are " +? ?????????????????????????"already consecutive"); ????????else ????????System.out.print(res); ????} } // This code is contributed by? // Manish Shaw(manishshaw1) ``` ## C# ```cs // C# program to find an element? // replacement of which makes? // the array elements consecutive. using System; using System.Linq; using System.Collections.Generic; class GFG { ????static int findElement(int []arr,? ???????????????????????????int n) ????{ ????????Array.Sort(arr); ????????// Making a series starting? ????????// from first element and? ????????// adding 1 to every element.? ????????int mismatch_count1 = 0, res = 0; ????????int next_element = arr[n - 1] - n + 1; ????????for (int i = 0; i < n - 1; i++)? ????????{ ????????if (Array.BinarySearch(arr,? ???????????????????????????????next_element) < 0) ????????{ ????????????res = arr[0];? ????????????mismatch_count1++; ????????} ????????????next_element++; ????????}? ????????// If only one mismatch is found. ????????if (mismatch_count1 == 1) ????????????return res; ????????// If no mismatch found, elements? ????????// are already consecutive. ????????if (mismatch_count1 == 0)? ????????????return 0; ????????// Making a series starting ????????// from last element and? ????????// subtracting 1 to every element.? ????????int mismatch_count2 = 0; ????????next_element = arr[0] + n - 1; ????????for (int i = n - 1; i >= 1; i--)? ????????{ ????????if (Array.BinarySearch(arr,? ???????????????????????????????next_element) < 0) ????????{ ????????????res = arr[n - 1];? ????????????mismatch_count2++; ????????}????? ????????next_element--; ????????} ????????// If only one mismatch is found. ????????if (mismatch_count2 == 1) ????????return res; ????????return -1;? ????} ????// Driver code ????static void Main() ????{ ????????int []arr = new int[]{7, 5, 12, 8} ; ????????int n = arr.Length; ????????int res = findElement(arr,n); ????????if (res == -1) ????????Console.Write("Answer does not exist"); ????????else if (res == 0) ????????Console.Write("Elements are " +? ??????????????????????"already consecutive"); ????????else ????????Console.Write(res); ????} } // This code is contributed by? // Manish Shaw(manishshaw1) ``` **輸出**： ``` 12 ``` **時間復雜度**：`O(N log N)` * * * * * *