查找丟失的號碼 · GeeksForGeeks 中文系列教程

# 查找丟失的號碼 > 原文： [https://www.geeksforgeeks.org/find-the-missing-number/](https://www.geeksforgeeks.org/find-the-missing-number/) 系統會為您提供 n-1 個整數的列表，這些整數在 1 到 n 的范圍內。列表中沒有重復項。列表中缺少整數之一。編寫有效的代碼以查找丟失的整數。 **示例**： ``` Input: arr[] = {1, 2, 4, 6, 3, 7, 8} Output: 5 Explanation: The missing number from 1 to 8 is 5 Input: arr[] = {1, 2, 3, 5} Output: 4 Explanation: The missing number from 1 to 5 is 4 ``` **方法 1** ：此方法使用求和公式的技術。 * **方法**：數組的長度為 n-1。因此，可以使用公式 *n *（n + 1）/ 2* 計算所有 n 個元素的總和，即從 1 到 n 的數字之和。現在找到數組中所有元素的總和，并從前 n 個自然數的總和中減去它，這將是缺失元素的值。 * **算法**： 1. 將前 n 個自然數的總和計算為 *sumtotal = n *（n + 1）/ 2* 2. 創建一個變量 sum 來存儲數組元素的和。 3. 從頭到尾遍歷數組。 4. 將 sum 的值更新為 *sum = sum + array [i]* 5. 將缺少的數字打印為*總和–總和* * **Implementation:** ## C++ ``` #include <bits/stdc++.h> using namespace std; // Function to get the missing number int getMissingNo(int a[], int n) { ????int total = (n + 1) * (n + 2) / 2; ????for (int i = 0; i < n; i++) ????????total -= a[i]; ????return total; } // Driver Code int main() { ????int arr[] = { 1, 2, 4, 5, 6 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int miss = getMissingNo(arr, n); ????cout << miss; } ``` ## C ``` #include <stdio.h> /* getMissingNo takes array and size of array as arguments*/ int getMissingNo(int a[], int n) { ????int i, total; ????total = (n + 1) * (n + 2) / 2; ????for (i = 0; i < n; i++) ????????total -= a[i]; ????return total; } /*program to test above function */ int main() { ????int a[] = { 1, 2, 4, 5, 6 }; ????int miss = getMissingNo(a, 5); ????printf("%d", miss); ????getchar(); } ``` ## Java ``` // Java program to find missing Number class Main { ????// Function to ind missing number ????static int getMissingNo(int a[], int n) ????{ ????????int i, total; ????????total = (n + 1) * (n + 2) / 2; ????????for (i = 0; i < n; i++) ????????????total -= a[i]; ????????return total; ????} ????/* program to test above function */ ????public static void main(String args[]) ????{ ????????int a[] = { 1, 2, 4, 5, 6 }; ????????int miss = getMissingNo(a, 5); ????????System.out.println(miss); ????} } ``` ## Python ``` # getMissingNo takes list as argument def getMissingNo(A): ????n = len(A) ????total = (n + 1)*(n + 2)/2 ????sum_of_A = sum(A) ????return total - sum_of_A # Driver program to test the above function A = [1, 2, 4, 5, 6] miss = getMissingNo(A) print(miss) # This code is contributed by Pratik Chhajer ``` ## C# ``` // C# program to find missing Number using System; class GFG { ????// Function to ind missing number ????static int getMissingNo(int[] a, int n) ????{ ????????int total = (n + 1) * (n + 2) / 2; ????????for (int i = 0; i < n; i++) ????????????total -= a[i]; ????????return total; ????} ????/* program to test above function */ ????public static void Main() ????{ ????????int[] a = { 1, 2, 4, 5, 6 }; ????????int miss = getMissingNo(a, 5); ????????Console.Write(miss); ????} } // This code is contributed by Sam007_ ``` ## PHP ``` <?php // PHP program to find // the Missing Number // getMissingNo takes array and // size of array as arguments function getMissingNo ($a, $n) { ????$total = ($n + 1) * ($n + 2) / 2;? ????for ( $i = 0; $i < $n; $i++) ????????$total -= $a[$i]; ????return $total; } // Driver Code $a = array(1, 2, 4, 5, 6); $miss = getMissingNo($a, 5); echo($miss); // This code is contributed by Ajit. ?> ``` **輸出**： ``` 3 ``` * **復雜度分析**： * **時間復雜度**：`O(n)`。僅需要遍歷數組。 * **空間復雜度**：`O(1)`。不需要多余的空間 **修改為溢出** * **方法**：方法保持不變，但是如果 n 大，則可能會溢出。為了避免整數溢出，請從已知數字中選擇一個數字，然后從給定數字中減去一個數字。這樣一來，就不會有整數溢出。 * **算法**： 1. 創建一個變量 *sum = 1* ，該變量將存儲缺少的數字，并創建一個計數器 *c = 2* 。 2. 從頭到尾遍歷數組。 3. 將 sum 的值更新為 *sum = sum – array [i] + c* ，將 c 更新為 *C++ * 。 4. 將缺少的數字打印為*和*。 * **實現**： ## C++ ``` #include <bits/stdc++.h> using namespace std; // a represents the array // n : Number of elements in array a int getMissingNo(int a[], int n)? {? ????int i, total=1;? ????for ( i = 2; i<= (n+1); i++) ????{ ????????total+=i; ????????total -= a[i-2]; ????} ????return total;? }? //Driver Program int main() { ????int arr[] = {1, 2, 3, 5}; ????cout<<getMissingNo(arr,sizeof(arr)/sizeof(arr[0])); ????return 0; } //This code is contributed by Ankur Goel ``` ## Java ``` // Java implementation? class GFG { ????// a represents the array ????// n : Number of elements in array a ????static int getMissingNo(int a[], int n)? ????{ ????????int total = 1; ????????for (int i = 2; i <= (n + 1); i++) ????????{ ????????????total += i; ????????????total -= a[i - 2]; ????????} ????????return total; ????} ????// Driver Code ????public static void main(String[] args) ????{ ????????int[] arr = { 1, 2, 3, 5 }; ????????System.out.println(getMissingNo(arr, arr.length)); ????} } // This post is contributed? // by Vivek Kumar Singh ``` ## Python3 ``` # a represents the array # n : Number of elements in array a def getMissingNo(a, n):? ????i, total = 0, 1 ????for i in range(2, n + 2): ????????total += i ????????total -= a[i - 2] ????return total # Driver Code arr = [1, 2, 3, 5] print(getMissingNo(arr, len(arr))) # This code is contributed by Mohit kumar ``` ## C# ``` using System; class GFG { // a represents the array // n : Number of elements in array a static int getMissingNo(int[] a, int n)? {? ????int i, total = 1;? ????for ( i = 2; i <= (n + 1); i++) ????{ ????????total += i; ????????total -= a[i - 2]; ????} ????return total;? }? // Driver Code public static void Main()? { ????int[] arr = {1, 2, 3, 5}; ????Console.Write(getMissingNo(arr, (arr.Length))); ????// Console.Write(getMissingNo(arr, 4)); } } // This code is contributed by SoumikMondal ``` * **復雜度分析**： * **時間復雜度**：`O(n)`。僅需要遍歷數組。 * **空間復雜度**：`O(1)`。不需要多余的空間 *感謝 Sahil Rally 提出的改進建議。* **方法 2** ：此方法使用 XOR 技術解決問題。 * **Approach:** *XOR has certain properties* * 假設 a1 ^ a2 ^ a3 ^…^ an = a 和 a1 ^ a2 ^ a3 ^…^ an-1 = b * 然后 a ^ b = an 使用此屬性，可以找到丟失的元素。計算從 1 到 n 的所有自然數的 XOR，并將其存儲為 a。現在，計算該數組所有元素的 XOR 并將其存儲為 b。缺少的數字將是 a ^ b。 *^* 是 XOR 運算符。 * **算法**： 1. 創建兩個變量 *a = 0* 和 *b = 0* 2. 以 i 為計數器從 1 到 n 循環運行。 3. 對于每個索引更新*，*為 *a = a ^ i* 4. 現在，從頭到尾遍歷數組。 5. 對于每個索引更新 *b* ，作為 *b = b ^ array [i]* 6. 將缺少的數字打印為 *a ^ b* 。 * **實現**： ## C++ ``` #include <bits/stdc++.h> using namespace std; // Function to get the missing number int getMissingNo(int a[], int n) { ????// For xor of all the elements in array ????int x1 = a[0]; ????// For xor of all the elements from 1 to n+1 ????int x2 = 1; ????for (int i = 1; i < n; i++) ????????x1 = x1 ^ a[i]; ????for (int i = 2; i <= n + 1; i++) ????????x2 = x2 ^ i; ????return (x1 ^ x2); } // Driver Code int main() { ????int arr[] = { 1, 2, 4, 5, 6 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int miss = getMissingNo(arr, n); ????cout << miss; } ``` ## C ``` #include <stdio.h> /* getMissingNo takes array and size of array as arguments*/ int getMissingNo(int a[], int n) { ????int i; ????int x1 = a[0]; /* For xor of all the elements in array */ ????int x2 = 1; /* For xor of all the elements from 1 to n+1 */ ????for (i = 1; i < n; i++) ????????x1 = x1 ^ a[i]; ????for (i = 2; i <= n + 1; i++) ????????x2 = x2 ^ i; ????return (x1 ^ x2); } /*program to test above function */ int main() { ????int a[] = { 1, 2, 4, 5, 6 }; ????int miss = getMissingNo(a, 5); ????printf("%d", miss); ????getchar(); } ``` ## Java ``` // Java program to find missing Number // using xor class Main { ????// Function to find missing number ????static int getMissingNo(int a[], int n) ????{ ????????int x1 = a[0]; ????????int x2 = 1; ????????/* For xor of all the elements? ???????????in array */ ????????for (int i = 1; i < n; i++) ????????????x1 = x1 ^ a[i]; ????????/* For xor of all the elements? ???????????from 1 to n+1 */ ????????for (int i = 2; i <= n + 1; i++) ????????????x2 = x2 ^ i; ????????return (x1 ^ x2); ????} ????/* program to test above function */ ????public static void main(String args[]) ????{ ????????int a[] = { 1, 2, 4, 5, 6 }; ????????int miss = getMissingNo(a, 5); ????????System.out.println(miss); ????} } ``` ## Python3 ``` # Python3 program to find # the mising Number # getMissingNo takes list as argument? def getMissingNo(a, n): ????x1 = a[0] ????x2 = 1 ????for i in range(1, n): ????????x1 = x1 ^ a[i] ????for i in range(2, n + 2): ????????x2 = x2 ^ i ????return x1 ^ x2 # Driver program to test above function if __name__=='__main__': ????a = [1, 2, 4, 5, 6] ????n = len(a) ????miss = getMissingNo(a, n)? ????print(miss) # This code is contributed by Yatin Gupta? ``` ## C# ``` // C# program to find missing Number // using xor using System; class GFG { ????// Function to find missing number ????static int getMissingNo(int[] a, int n) ????{ ????????int x1 = a[0]; ????????int x2 = 1; ????????/* For xor of all the elements? ????????in array */ ????????for (int i = 1; i < n; i++) ????????????x1 = x1 ^ a[i]; ????????/* For xor of all the elements? ????????from 1 to n+1 */ ????????for (int i = 2; i <= n + 1; i++) ????????????x2 = x2 ^ i; ????????return (x1 ^ x2); ????} ????/* driver program to test above function */ ????public static void Main() ????{ ????????int[] a = { 1, 2, 4, 5, 6 }; ????????int miss = getMissingNo(a, 5); ????????Console.Write(miss); ????} } // This code is contributed by Sam007_ ``` ## PHP ``` <?php // PHP program to find // the Misiing Number // getMissingNo takes array and? // size of array as arguments function getMissingNo($a, $n) { ????// For xor of all the ????// elements in array? ????$x1 = $a[0];? ????// For xor of all the? ????// elements from 1 to n + 1 ????$x2 = 1;? ????for ($i = 1; $i < $n; $i++) ????????$x1 = $x1 ^ $a[$i]; ????for ($i = 2; $i <= $n + 1; $i++) ????????$x2 = $x2 ^ $i;????? ????return ($x1 ^ $x2); } // Driver Code $a = array(1, 2, 4, 5, 6); $miss = getMissingNo($a, 5); echo($miss); // This code is contributed by Ajit. ?> ``` **輸出**： ``` 3 ``` * **復雜度分析**： * **時間復雜度**：`O(n)`。僅需要遍歷數組。 * **空間復雜度**：`O(1)`。不需要多余的空間。