查找 1 到 n-1 之間的唯一重復元素 · GeeksForGeeks 中文系列教程

# 查找 1 到 n-1 之間的唯一重復元素 > 原文： [https://www.geeksforgeeks.org/find-repetitive-element-1-n-1/](https://www.geeksforgeeks.org/find-repetitive-element-1-n-1/) 給我們一個大小為 n 的數組 arr []。數字從 1 到（n-1）以隨機順序排列。該數組只有一個重復元素。我們需要找到重復元素。 **示例**： ``` Input : a[] = {1, 3, 2, 3, 4} Output : 3 Input : a[] = {1, 5, 1, 2, 3, 4} Output : 1 ``` **方法 1（簡單）**我們使用兩個嵌套循環。外循環遍歷所有元素，內循環檢查外循環拾取的元素是否出現在其他任何地方。 **時間復雜度**： O（n * n） **方法 2（使用求和公式）**：我們知道[前 n-1 個自然數](https://www.geeksforgeeks.org/program-find-sum-first-n-natural-numbers/)的和為（n – 1）* n / 2。我們計算數組元素的總和，并從中減去自然數總和，以找到唯一的缺失元素。 ## C++ ```cpp // CPP program to find the only repeating // element in an array where elements are // from 1 to n-1\. #include <bits/stdc++.h> using namespace std; int findRepeating(int arr[], int n) { ???// Find array sum and subtract sum ???// first n-1 natural numbers from it ???// to find the result. ???return accumulate(arr , arr+n , 0) -? ???????????????????((n - 1) * n/2); } // driver code int main() {??? ????int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << findRepeating(arr, n); ????return 0; } ``` ## Java ```java // Java program to find the only repeating? // element in an array where elements are? // from 1 to n-1\. import java.io.*; import java.util.*;? class GFG? { ????static int findRepeating(int[] arr, int n) ????{ ????????// Find array sum and subtract sum? ????????// first n-1 natural numbers from it? ????????// to find the result. ????????int sum = 0; ????????for (int i = 0; i < n; i++) ????????????sum += arr[i]; ????????return sum - (((n - 1) * n) / 2);? ????} ????// Driver code ????public static void main(String args[])? ????{ ????????int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; ????????int n = arr.length; ????????System.out.println(findRepeating(arr, n)); ????} } // This code is contributed by rachana soma ``` ## Python3 ```py # Python3 program to find the only? # repeating element in an array where? # elements are from 1 to n-1\. def findRepeating(arr, n): ????# Find array sum and subtract sum ????# first n-1 natural numbers from it ????# to find the result. ????return sum(arr) -(((n - 1) * n) // 2) # Driver Code arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7] n = len(arr) print(findRepeating(arr, n)) # This code is contributed? # by mohit kumar ``` ## C# ```cs // C# program to find the only repeating? // element in an array where elements are? // from 1 to n-1\. using System;? class GFG? { ????static int findRepeating(int[] arr, int n) ????{ ????????// Find array sum and subtract sum? ????????// first n-1 natural numbers from it? ????????// to find the result. ????????int sum = 0; ????????for (int i = 0; i < n; i++) ????????????sum += arr[i]; ????????return sum - (((n - 1) * n) / 2);? ????} ????// Driver code ????public static void Main(String []args)? ????{ ????????int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; ????????int n = arr.Length; ????????Console.WriteLine(findRepeating(arr, n)); ????} } /* This code contributed by PrinciRaj1992 */ ``` **輸出**： ``` 8 ``` **時間復雜度**：`O(n)` **輔助空間**：`O(1)` 導致大型數組溢出。 **方法 3（使用散列）**：使用散列表存儲已訪問的元素。如果看到的元素再次出現，我們將其返回。 ## C++ ``` // CPP program to find the only repeating // element in an array where elements are // from 1 to n-1\. #include <bits/stdc++.h> using namespace std; int findRepeating(int arr[], int n) { ???unordered_set<int> s; ???for (int i=0; i<n; i++) ???{ ??????if (s.find(arr[i]) != s.end()) ?????????return arr[i]; ??????s.insert(arr[i]); ???} ???// If input is correct, we should? ???// never reach here ???return -1; } // driver code int main() {??? ????int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << findRepeating(arr, n); ????return 0; } ``` ## Java ```java import java.util.*; // Java program to find the only repeating? // element in an array where elements are? // from 1 to n-1\. class GFG? { static int findRepeating(int arr[], int n)? {? ????HashSet<Integer> s = new HashSet<Integer>(); ????for (int i = 0; i < n; i++)? ????{? ????????if (s.contains(arr[i]))? ????????????return arr[i];? ????????s.add(arr[i]);? ????}? ????// If input is correct, we should? ????// never reach here? ????return -1;? }? // Driver code? public static void main(String[] args)? { ????int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };? ????int n = arr.length; ????System.out.println(findRepeating(arr, n));; } } // This code is contributed by Rajput-Ji ``` ## Python3 ```py # Python3 program to find the only? # repeating element in an array? # where elements are from 1 to n-1.? def findRepeating(arr, n): ????s = set() ????for i in range(n): ????????if arr[i] in s: ????????????return arr[i] ????????s.add(arr[i]) ????# If input is correct, we should? ????# never reach here? ????rteurn -1 # Driver code arr = [9, 8, 2, 6, 1, 8, 5, 3] n = len(arr) print(findRepeating(arr, n)) # This code is contributed? # by Shrikant13 ``` ## C# ``` // C# program to find the only repeating? // element in an array where elements are? // from 1 to n-1\. using System; using System.Collections.Generic; class GFG? { static int findRepeating(int []arr, int n)? {? ????HashSet<int> s = new HashSet<int>(); ????for (int i = 0; i < n; i++)? ????{? ????????if (s.Contains(arr[i]))? ????????????return arr[i];? ????????s.Add(arr[i]);? ????}? ????// If input is correct, we should? ????// never reach here? ????return -1;? }? // Driver code? public static void Main(String[] args)? { ????int []arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };? ????int n = arr.Length; ????Console.WriteLine(findRepeating(arr, n));; } } // This code has been contributed by 29AjayKumar ``` **輸出**： ``` 8 ``` **時間復雜度**：`O(n)` **輔助空間**：`O(n)` **方法 4（使用 XOR）**：該思想基于以下事實：x ^ x = 0 且 x ^ y = y ^ x。 1）計算從 1 到 n-1 的元素的 XOR。 2）計算數組元素的 XOR。 3）以上兩項的異或將是我們的結果。 ## C++ ``` // CPP program to find the only repeating // element in an array where elements are // from 1 to n-1\. #include <bits/stdc++.h> using namespace std; int findRepeating(int arr[], int n) { ???// res is going to store value of ???// 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^? ???// arr[1] ^ .... arr[n-1] ???int res = 0; ???for (int i=0; i<n-1; i++) ???????res = res ^ (i+1) ^ arr[i]; ???res = res ^ arr[n-1]; ???return res; } // driver code int main() {??? ????int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << findRepeating(arr, n); ????return 0; } ```