檢查數組元素是否連續新增方法 3 · GeeksForGeeks 中文系列教程

# 檢查數組元素是否連續新增方法 3 > 原文： [https://www.geeksforgeeks.org/check-if-array-elements-are-consecutive/](https://www.geeksforgeeks.org/check-if-array-elements-are-consecutive/) 給定一個未排序的數字數組，編寫一個函數，如果該數組包含連續的數字，則該函數返回 true。 **示例**： **a）**如果數組為{5，2，3，1，4}，則該函數應返回 true，因為數組具有從 1 到 5 的連續數字。 **b）**如果數組為{83，78，80，81，79，82}，則該函數應返回 true，因為數組具有從 78 到 83 的連續數字。 **c）**如果數組是{34，23，52，12，3}，則該函數應返回 false，因為元素不連續。 **d）**如果數組是{7，6，5，5，5，3，4}，則該函數應返回 false，因為 5 和 5 不連續。 **方法 1（使用排序）** 1）對所有元素進行排序。 2）對排序后的數組進行線性掃描。如果當前元素和下一個元素之間的差不是 1，則返回 false。如果所有差異均為 1，則返回 true。時間復雜度：O（nLogn） **方法 2（使用訪問數組）** 這個想法是要檢查以下兩個條件。如果滿足以下兩個條件，則返回 true。 1） *max-min + 1 = n* 其中 max 是數組中的最大元素，min 是數組中的最小元素，n 是數組中的元素數。 2）所有元素都是不同的。要檢查所有元素是否都不同，我們可以創建大小為 n 的 visited []數組。我們可以使用 arr [i]-min 作為 Visited []中的索引，將輸入數組 arr []的第 i 個元素映射到訪問數組。 ## C++ ```cpp #include<stdio.h> #include<stdlib.h> /* Helper functions to get minimum and maximum in an array */ int getMin(int arr[], int n); int getMax(int arr[], int n); /* The function checks if the array elements are consecutive ??If elements are consecutive, then returns true, else returns ??false */ bool areConsecutive(int arr[], int n) { ??if ( n <? 1 ) ????return false; ??/* 1) Get the minimum element in array */ ??int min = getMin(arr, n); ??/* 2) Get the maximum element in array */ ??int max = getMax(arr, n); ??/* 3) max - min + 1 is equal to n,? then only check all elements */ ??if (max - min? + 1 == n) ??{ ??????/* Create a temp array to hold visited flag of all elements. ?????????Note that, calloc is used here so that all values are initialized? ?????????as false */? ??????bool *visited = (bool *) calloc (n, sizeof(bool)); ??????int i; ??????for (i = 0; i < n; i++) ??????{ ?????????/* If we see an element again, then return false */ ?????????if ( visited[arr[i] - min] != false ) ???????????return false; ?????????/* If visited first time, then mark the element as visited */ ?????????visited[arr[i] - min] = true; ??????} ??????/* If all elements occur once, then return true */ ??????return true; ??} ??return false; // if (max - min? + 1 != n) } /* UTILITY FUNCTIONS */ int getMin(int arr[], int n) { ??int min = arr[0]; ??for (int i = 1; i < n; i++) ???if (arr[i] < min) ?????min = arr[i]; ??return min; } int getMax(int arr[], int n) { ??int max = arr[0]; ??for (int i = 1; i < n; i++) ???if (arr[i] > max) ?????max = arr[i]; ??return max; } /* Driver program to test above functions */ int main() { ????int arr[]= {5, 4, 2, 3, 1, 6}; ????int n = sizeof(arr)/sizeof(arr[0]); ????if(areConsecutive(arr, n) == true) ????????printf(" Array elements are consecutive "); ????else ????????printf(" Array elements are not consecutive "); ????getchar(); ????return 0; } ``` ## Java ```java class AreConsecutive? { ????/* The function checks if the array elements are consecutive ???????If elements are consecutive, then returns true, else returns ???????false */ ????boolean areConsecutive(int arr[], int n)? ????{ ????????if (n < 1) ????????????return false; ????????/* 1) Get the minimum element in array */ ????????int min = getMin(arr, n); ????????/* 2) Get the maximum element in array */ ????????int max = getMax(arr, n); ????????/* 3) max - min + 1 is equal to n,? then only check all elements */ ????????if (max - min + 1 == n)? ????????{ ????????????/* Create a temp array to hold visited flag of all elements. ???????????????Note that, calloc is used here so that all values are initialized? ???????????????as false */ ????????????boolean visited[] = new boolean[n]; ????????????int i; ????????????for (i = 0; i < n; i++)? ????????????{ ????????????????/* If we see an element again, then return false */ ????????????????if (visited[arr[i] - min] != false) ????????????????????return false; ????????????????/* If visited first time, then mark the element as visited */ ????????????????visited[arr[i] - min] = true; ????????????} ????????????/* If all elements occur once, then return true */ ????????????return true; ????????} ????????return false; // if (max - min? + 1 != n) ????} ????/* UTILITY FUNCTIONS */ ????int getMin(int arr[], int n)? ????{ ????????int min = arr[0]; ????????for (int i = 1; i < n; i++)? ????????{ ????????????if (arr[i] < min) ????????????????min = arr[i]; ????????} ????????return min; ????} ????int getMax(int arr[], int n)? ????{ ????????int max = arr[0]; ????????for (int i = 1; i < n; i++)? ????????{ ????????????if (arr[i] > max) ????????????????max = arr[i]; ????????} ????????return max; ????} ????/* Driver program to test above functions */ ????public static void main(String[] args)? ????{ ????????AreConsecutive consecutive = new AreConsecutive(); ????????int arr[] = {5, 4, 2, 3, 1, 6}; ????????int n = arr.length; ????????if (consecutive.areConsecutive(arr, n) == true) ????????????System.out.println("Array elements are consecutive"); ????????else ????????????System.out.println("Array elements are not consecutive"); ????} } // This code has been contributed by Mayank Jaiswal ``` ## Python3 ```py # Helper functions to get Minimum and # Maximum in an array? # The function checks if the array elements? # are consecutive. If elements are consecutive,? # then returns true, else returns false? def areConsecutive(arr, n): ????if ( n < 1 ): ????????return False ????# 1) Get the Minimum element in array */ ????Min = min(arr) ????# 2) Get the Maximum element in array */ ????Max = max(arr) ????# 3) Max - Min + 1 is equal to n,? ????# then only check all elements */ ????if (Max - Min + 1 == n): ????????# Create a temp array to hold visited? ????????# flag of all elements. Note that, calloc? ????????# is used here so that all values are? ????????# initialized as false ????????visited = [False for i in range(n)] ????????for i in range(n): ????????????# If we see an element again,? ????????????# then return false */ ????????????if (visited[arr[i] - Min] != False): ????????????????return False ????????????# If visited first time, then mark ????????????# the element as visited */ ????????????visited[arr[i] - Min] = True ????????# If all elements occur once, ????????# then return true */ ????????return True ????return False # if (Max - Min + 1 != n) # Driver Code arr = [5, 4, 2, 3, 1, 6] n = len(arr) if(areConsecutive(arr, n) == True): ????print("Array elements are consecutive ") else: ????print("Array elements are not consecutive ") # This code is contributed by mohit kumar ``` ## C# ```cs using System; class GFG { ????/* The function checks if the array elements ????are consecutive If elements are consecutive, ????then returns true, else returns??? false */ ????static bool areConsecutive(int []arr, int n)? ????{ ????????if (n < 1) ????????????return false; ????????/* 1) Get the minimum element in array */ ????????int min = getMin(arr, n); ????????/* 2) Get the maximum element in array */ ????????int max = getMax(arr, n); ????????/* 3) max - min + 1 is equal to n, then? ????????only check all elements */ ????????if (max - min + 1 == n)? ????????{ ????????????/* Create a temp array to hold visited ????????????flag of all elements. Note that, calloc ????????????is used here so that all values are ????????????initialized as false */ ????????????bool []visited = new bool[n]; ????????????int i; ????????????for (i = 0; i < n; i++)? ????????????{ ????????????????/* If we see an element again, then ????????????????return false */ ????????????????if (visited[arr[i] - min] != false) ????????????????????return false; ????????????????/* If visited first time, then mark? ????????????????the element as visited */ ????????????????visited[arr[i] - min] = true; ????????????} ????????????/* If all elements occur once, then ????????????return true */ ????????????return true; ????????} ????????return false; // if (max - min + 1 != n) ????} ????/* UTILITY FUNCTIONS */ ????static int getMin(int []arr, int n)? ????{ ????????int min = arr[0]; ????????for (int i = 1; i < n; i++)? ????????{ ????????????if (arr[i] < min) ????????????????min = arr[i]; ????????} ????????return min; ????} ????static int getMax(int []arr, int n)? ????{ ????????int max = arr[0]; ????????for (int i = 1; i < n; i++)? ????????{ ????????????if (arr[i] > max) ????????????????max = arr[i]; ????????} ????????return max; ????} ????/* Driver program to test above functions */ ????public static void Main()? ????{ ????????int []arr = {5, 4, 2, 3, 1, 6}; ????????int n = arr.Length; ????????if (areConsecutive(arr, n) == true) ????????????Console.Write("Array elements are" ??????????????????????????????+ " consecutive"); ????????else ????????????Console.Write("Array elements are" ?????????????????????????+ " not consecutive"); ????} } // This code is contributed by nitin mittal. ``` ## PHP ```php <?php // PHP Program for above approach // The function checks if the array elements? // are consecutive. If elements are consecutive,? // then returns true, else returns false? function areConsecutive($arr, $n)? {? ????if ( $n < 1 )? ????????return false;? ????// 1) Get the minimum element in array? ????$min = getMin($arr, $n);? ????// 2) Get the maximum element in array? ????$max = getMax($arr, $n);? ????// 3) $max - $min + 1 is equal to $n,? ????// then only check all elements? ????if ($max - $min + 1 == $n)? ????{? ????????// Create a temp array to hold? ????????// visited flag of all elements. ????????$visited = array();? ????????for ($i = 0; $i < $n; $i++)? ????????{? ????????????$visited[$i] = false;? ????????}? ????????for ($i = 0; $i < $n; $i++)? ????????{? ????????????// If we see an element again,? ????????????// then return false? ????????????if ( $visited[$arr[$i] - $min] != false )? ????????????return false;? ????????????// If visited first time, then mark? ????????????// the element as visited ????????????$visited[$arr[$i] - $min] = true;? ????????}? ????????// If all elements occur once,? ????????// then return true? ????????return true;? ????}? ????return false; // if ($max - $min + 1 != $n)? }? // UTILITY FUNCTIONS? function getMin($arr, $n)? {? ????$min = $arr[0];? ????for ($i = 1; $i < $n; $i++)? ????????if ($arr[$i] < $min)? ????????????$min = $arr[$i];? ????return $min;? }? function getMax($arr, $n)? {? ????$max = $arr[0];? ????for ($i = 1; $i < $n; $i++)? ????????if ($arr[$i] > $max)? ????????????$max = $arr[$i];? ????return $max;? }? // Driver Code $arr = array(5, 4, 2, 3, 1, 6);? $n = count($arr); if(areConsecutive($arr, $n) == true)? ????echo "Array elements are consecutive ";? else ????echo "Array elements are not consecutive ";? // This code is contributed by rathbhupendra ?> ``` **時間復雜度**：`O(n)` **額外空間**：`O(n)` **方法 3（將訪問的數組元素標記為負）** 此方法具有`O(n)`時間復雜度和`O(1)`額外空間，但是它更改了原始數組，并且僅當所有數字均為正。我們可以通過添加一個額外的步驟來獲得原始數組。它是方法 2 的擴展，具有相同的兩個步驟。 1） *max-min + 1 = n* 其中 max 是數組中的最大元素，min 是數組中的最小元素，n 是數組中的元素數。 2）所有元素都是不同的。在此方法中，步驟 2 的實現與方法 2 不同。我們沒有創建新的數組，而是修改了輸入數組 arr []來跟蹤訪問的元素。這個想法是遍歷數組，對于每個索引 i（其中 0≤i < n），將 arr [arr [i] – min]]設為負值。如果我們再次看到負值，則說明存在重復。 ## C++ ``` #include<stdio.h> #include<stdlib.h> /* Helper functions to get minimum and maximum in an array */ int getMin(int arr[], int n); int getMax(int arr[], int n); /* The function checks if the array elements are consecutive ??If elements are consecutive, then returns true, else returns ??false */ bool areConsecutive(int arr[], int n) { ????if ( n <? 1 ) ????????return false; ????/* 1) Get the minimum element in array */ ????int min = getMin(arr, n); ????/* 2) Get the maximum element in array */ ????int max = getMax(arr, n); ????/* 3) max - min + 1 is equal to n then only check all elements */ ????if (max - min? + 1 == n) ????{ ????????int i; ????????for(i = 0; i < n; i++) ????????{ ????????????int j; ????????????if (arr[i] < 0) ????????????????j = -arr[i] - min; ????????????else ????????????????j = arr[i] - min; ????????????// if the value at index j is negative then ????????????// there is repetition ????????????if (arr[j] > 0) ????????????????arr[j] = -arr[j]; ????????????else ????????????????return false; ????????} ????????/* If we do not see a negative value then all elements ???????????are distinct */ ????????return true; ????} ????return false; // if (max - min? + 1 != n) } /* UTILITY FUNCTIONS */ int getMin(int arr[], int n) { ????int min = arr[0]; ????for (int i = 1; i < n; i++) ????????if (arr[i] < min) ????????????min = arr[i]; ????return min; } int getMax(int arr[], int n) { ????int max = arr[0]; ????for (int i = 1; i < n; i++) ????????if (arr[i] > max) ????????????max = arr[i]; ????return max; } /* Driver program to test above functions */ int main() { ????int arr[]= {1, 4, 5, 3, 2, 6}; ????int n = sizeof(arr)/sizeof(arr[0]); ????if(areConsecutive(arr, n) == true) ????????printf(" Array elements are consecutive "); ????else ????????printf(" Array elements are not consecutive "); ????getchar(); ????return 0; } ```