# 找到重復的和丟失的| 添加了 3 種新方法 > 原文： [https://www.geeksforgeeks.org/find-a-repeating-and-a-missing-number/](https://www.geeksforgeeks.org/find-a-repeating-and-a-missing-number/) 給定大小為 n 的未排序數組。 數組元素的范圍是 1 到 n。 集合{1，2??，…n}中的一個數字丟失，并且一個數字在數組中出現兩次。 找到這兩個數字。 **示例**： ``` Input: arr[] = {3, 1, 3} Output: Missing = 2, Repeating = 3 Explanation: In the array, 2 is missing and 3 occurs twice Input: arr[] = {4, 3, 6, 2, 1, 1} Output: Missing = 5, Repeating = 1 ``` **以下是解決問題的各種方法**： * **Method 1 (Use Sorting)** **方法**： 1. 對輸入數組進行排序。 2. 遍歷數組并檢查是否丟失和重復。 **時間復雜度**： O（nLogn） 感謝 **LoneShadow** 提出了此方法。 * **Method 2 (Use count array)** **Approach:** 1. 創建一個大小為 n 的臨時數組 temp []，所有初始值均為 0。 2. 遍歷輸入數組 arr []，并對每個 arr [i]執行以下操作 * if（temp [arr [i]] == 0）temp [arr [i]] = 1; * if（temp [arr [i]] == 1）輸出“ arr [i]” //重復 3. 遍歷 temp []并輸出值為 0 的數組元素（這是缺少的元素） **時間復雜度**：`O(n)` **輔助空間**：`O(n)` * **Method 3 (Use elements as Index and mark the visited places)** **方法**： 遍歷數組。 遍歷時，將每個元素的絕對值用作索引，并使該索引處的值為負，以將其標記為已訪問。 如果某些內容已標記為否，則為重復元素。 要查找丟失的內容，請再次遍歷數組并尋找一個正值。 ## C++ ``` // C++ program to Find the repeating // and missing elements #include <bits/stdc++.h> using namespace std; void printTwoElements(int arr[], int size) { ????int i; ????cout << " The repeating element is "; ????for (i = 0; i < size; i++) { ????????if (arr[abs(arr[i]) - 1] > 0) ????????????arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]; ????????else ????????????cout << abs(arr[i]) << "\n"; ????} ????cout << "and the missing element is "; ????for (i = 0; i < size; i++) { ????????if (arr[i] > 0) ????????????cout << (i + 1); ????} } /* Driver code */ int main() { ????int arr[] = { 7, 3, 4, 5, 5, 6, 2 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????printTwoElements(arr, n); } // This code is contributed by Shivi_Aggarwal ``` ## C ``` // C program to Find the repeating // and missing elements #include <stdio.h> #include <stdlib.h> void printTwoElements(int arr[], int size) { ????int i; ????printf("\n The repeating element is"); ????for (i = 0; i < size; i++) { ????????if (arr[abs(arr[i]) - 1] > 0) ????????????arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]; ????????else ????????????printf(" %d ", abs(arr[i])); ????} ????printf("\nand the missing element is "); ????for (i = 0; i < size; i++) { ????????if (arr[i] > 0) ????????????printf("%d", i + 1); ????} } // Driver code int main() { ????int arr[] = { 7, 3, 4, 5, 5, 6, 2 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????printTwoElements(arr, n); ????return 0; } ``` ## Java ``` // Java program to Find the repeating // and missing elements import java.io.*; class GFG { ????static void printTwoElements(int arr[], int size) ????{ ????????int i; ????????System.out.print("The repeating element is "); ????????for (i = 0; i < size; i++) { ????????????int abs_val = Math.abs(arr[i]); ????????????if (arr[abs_val - 1] > 0) ????????????????arr[abs_val - 1] = -arr[abs_val - 1]; ????????????else ????????????????System.out.println(abs_val); ????????} ????????System.out.print("And the missing element is "); ????????for (i = 0; i < size; i++) { ????????????if (arr[i] > 0) ????????????????System.out.println(i + 1); ????????} ????} ????// Driver code ????public static void main(String[] args) ????{ ????????int arr[] = { 7, 3, 4, 5, 5, 6, 2 }; ????????int n = arr.length; ????????printTwoElements(arr, n); ????} } // This code is contributed by Gitanjali ``` ## Python3 ``` # Python3 code to Find the repeating? # and the missing elements def printTwoElements( arr, size): ????for i in range(size): ????????if arr[abs(arr[i])-1] > 0: ????????????arr[abs(arr[i])-1] = -arr[abs(arr[i])-1] ????????else: ????????????print("The repeating element is", abs(arr[i])) ????for i in range(size): ????????if arr[i]>0: ????????????print("and the missing element is", i + 1) # Driver program to test above function */ arr = [7, 3, 4, 5, 5, 6, 2] n = len(arr) printTwoElements(arr, n) # This code is contributed by "Abhishek Sharma 44" ``` ## C# ``` // C# program to Find the repeating // and missing elements using System; class GFG { ????static void printTwoElements(int[] arr, int size) ????{ ????????int i; ????????Console.Write("The repeating element is "); ????????for (i = 0; i < size; i++) { ????????????int abs_val = Math.Abs(arr[i]); ????????????if (arr[abs_val - 1] > 0) ????????????????arr[abs_val - 1] = -arr[abs_val - 1]; ????????????else ????????????????Console.WriteLine(abs_val); ????????} ????????Console.Write("And the missing element is "); ????????for (i = 0; i < size; i++) { ????????????if (arr[i] > 0) ????????????????Console.WriteLine(i + 1); ????????} ????} ????// Driver program ????public static void Main() ????{ ????????int[] arr = { 7, 3, 4, 5, 5, 6, 2 }; ????????int n = arr.Length; ????????printTwoElements(arr, n); ????} } // This code is contributed by Sam007 ``` ## PHP ``` <?php // PHP program to Find the repeating // and missing elements function printTwoElements($arr, $size) { ????$i; ????echo "The repeating element is", " "; ????for($i = 0; $i < $size; $i++) ????{ ????????if($arr[abs($arr[$i]) - 1] > 0) ????????????$arr[abs($arr[$i]) - 1] =? ????????????- $arr[abs($arr[$i]) - 1]; ????????else ????????????echo ( abs($arr[$i])); ????} ????echo "\nand the missing element is "; ????for($i = 0; $i < $size; $i++) ????{ ????????if($arr[$i] > 0) ????????????echo($i + 1); ????} } ????// Driver Code ????$arr = array(7, 3, 4, 5, 5, 6, 2); ????$n = count($arr); ????printTwoElements($arr, $n); // This code is contributed by anuj_67\. ?> ``` **輸出**： ``` The repeating element is 5 and the missing element is 1 ``` **時間復雜度**：`O(n)` 感謝 **Manish Mishra** 提出了此方法。 * **Method 4 (Make two equations)** **Approach:** 1. 令 x 為缺失元素，y 為重復元素。 2. 使用公式**獲得所有數字的總和 S = n（n + 1）/ 2 – x + y** 3. 使用公式**獲得所有數字的乘積 P = 1 * 2 * 3 * ... * n * y / x** 4. 上面的兩個步驟為我們提供了兩個方程，我們可以求解方程并獲得 x 和 y 的值。 **Time Complexity:** O(n) 感謝**消失了**提出了這種解決方案。 **注意**：當我們計算所有數組元素的乘積和總和時，此方法可能導致算術溢出。 * **Method 5 (Use XOR)** **Approach:** * 令 x 和 y 為所需的輸出元素。 * Calculate XOR of all the array elements. > **xor1 = arr [0] ^ arr [1] ^ arr [2] ..... arr [n-1]** * XOR the result with all numbers from 1 to n > **xor1 = xor1 ^ 1 ^ 2 ^ ..... ^ n** * 在結果 *xor1* 中，除 x 和 y 外，所有元素都將彼此作廢。 *xor1* 中設置的所有位都將設置為 x 或 y。 因此，如果我們取 *xor1* 的任何設置位（我們在代碼中選擇了最右邊的設置位），然后將數組的元素分為兩組-一組具有相同位的元素，而另一組具有相同的位 位未設置。 這樣，我們將在一組中獲得 x，在另一組中獲得 y。 現在，如果我們對第一個集合中的所有元素進行 XOR，我們將得到 x，而在其他集合中進行同樣的操作，我們將得到 y。 下面是上述方法的實現： ## C++ ``` // C++ program to Find the repeating // and missing elements #include <bits/stdc++.h> using namespace std; /* The output of this function is stored at *x and *y */ void getTwoElements(int arr[], int n, ????????????????????int* x, int* y) { ????/* Will hold xor of all elements? ????and numbers from 1 to n */ ????int xor1; ????/* Will have only single set bit of xor1 */ ????int set_bit_no; ????int i; ????*x = 0; ????*y = 0; ????xor1 = arr[0]; ????/* Get the xor of all array elements */ ????for (i = 1; i < n; i++) ????????xor1 = xor1 ^ arr[i]; ????/* XOR the previous result with numbers? ????from 1 to n*/ ????for (i = 1; i <= n; i++) ????????xor1 = xor1 ^ i; ????/* Get the rightmost set bit in set_bit_no */ ????set_bit_no = xor1 & ~(xor1 - 1); ????/* Now divide elements into two? ????sets by comparing a rightmost set ????bit of xor1 with the bit at the same? ????position in each element. Also,? ????get XORs of two sets. The two ????XORs are the output elements.? ????The following two for loops? ????serve the purpose */ ????for (i = 0; i < n; i++) { ????????if (arr[i] & set_bit_no) ????????????/* arr[i] belongs to first set */ ????????????*x = *x ^ arr[i]; ????????else ????????????/* arr[i] belongs to second set*/ ????????????*y = *y ^ arr[i]; ????} ????for (i = 1; i <= n; i++) { ????????if (i & set_bit_no) ????????????/* i belongs to first set */ ????????????*x = *x ^ i; ????????else ????????????/* i belongs to second set*/ ????????????*y = *y ^ i; ????} ????/* *x and *y hold the desired ????????output elements */ } /* Driver code */ int main() { ????int arr[] = { 1, 3, 4, 5, 5, 6, 2 }; ????int* x = (int*)malloc(sizeof(int)); ????int* y = (int*)malloc(sizeof(int)); ????int n = sizeof(arr) / sizeof(arr[0]); ????getTwoElements(arr, n, x, y); ????cout << " The missing element is " << *x << " and the repeating" ?????????<< " number is " << *y; ????getchar(); } // This code is contributed by Code_Mech ```