非重復元素 · GeeksForGeeks 中文系列教程

# 非重復元素 > 原文： [https://www.geeksforgeeks.org/non-repeating-element/](https://www.geeksforgeeks.org/non-repeating-element/) 在給定的整數數組中找到第一個非重復元素。 **示例**： ``` Input : -1 2 -1 3 2 Output : 3 Explanation : The first number that does not repeat is : 3 Input : 9 4 9 6 7 4 Output : 6 ``` **簡單解決方案**是使用兩個循環。外循環一個接一個地挑選元素，內循環檢查該元素是否存在一次以上。 ## C++ ```cpp // Simple CPP program to find first non- // repeating element. #include <bits/stdc++.h> using namespace std; int firstNonRepeating(int arr[], int n) { ????for (int i = 0; i < n; i++) { ????????int j; ????????for (j = 0; j < n; j++) ????????????if (i != j && arr[i] == arr[j]) ????????????????break; ????????if (j == n) ????????????return arr[i]; ????} ????return -1; } // Driver code int main() { ????int arr[] = { 9, 4, 9, 6, 7, 4 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << firstNonRepeating(arr, n); ????return 0; } ``` ## Java ```java // Java program to find first non-repeating // element. class GFG { ????static int firstNonRepeating(int arr[], int n) ????{ ????????for (int i = 0; i < n; i++) { ????????????int j; ????????????for (j = 0; j < n; j++) ????????????????if (i != j && arr[i] == arr[j]) ????????????????????break; ????????????if (j == n) ????????????????return arr[i]; ????????} ????????return -1; ????} ????// Driver code ????public static void main(String[] args) ????{ ????????int arr[] = { 9, 4, 9, 6, 7, 4 }; ????????int n = arr.length; ????????System.out.print(firstNonRepeating(arr, n)); ????} } // This code is contributed by Anant Agarwal. ``` ## Python3 ```py # Python3 program to find first? # non-repeating element. def firstNonRepeating(arr, n): ????for i in range(n): ????????j = 0 ????????while(j < n): ????????????if (i != j and arr[i] == arr[j]): ????????????????break ????????????j += 1 ????????if (j == n): ????????????return arr[i] ????return -1 # Driver code arr = [ 9, 4, 9, 6, 7, 4 ] n = len(arr) print(firstNonRepeating(arr, n)) # This code is contributed by Anant Agarwal. ``` ## C# ```cs // C# program to find first non- // repeating element. using System; class GFG { ????static int firstNonRepeating(int[] arr, int n) ????{ ????????for (int i = 0; i < n; i++) { ????????????int j; ????????????for (j = 0; j < n; j++) ????????????????if (i != j && arr[i] == arr[j]) ????????????????????break; ????????????if (j == n) ????????????????return arr[i]; ????????} ????????return -1; ????} ????// Driver code ????public static void Main() ????{ ????????int[] arr = { 9, 4, 9, 6, 7, 4 }; ????????int n = arr.Length; ????????Console.Write(firstNonRepeating(arr, n)); ????} } // This code is contributed by Anant Agarwal. ``` ## PHP ```php <?php // Simple PHP program to find first non- // repeating element. function firstNonRepeating($arr, $n) { ????for ($i = 0; $i < $n; $i++) ????{ ????????$j; ????????for ($j = 0; $j< $n; $j++) ????????????if ($i != $j && $arr[$i] == $arr[$j]) ????????????????break; ????????if ($j == $n) ????????????return $arr[$i]; ????} ????return -1; } ????// Driver code ????$arr = array(9, 4, 9, 6, 7, 4); ????$n = sizeof($arr) ; ????echo firstNonRepeating($arr, $n); // This code is contributed by ajit ?> ``` **輸出**： ``` 6 ``` **有效解決方案**將使用哈希。 1）在哈希表中遍歷數組和插入元素及其計數。 2）再次遍歷數組，并打印計數等于 1 的第一個元素。 ## C++ ``` // Efficient CPP program to find first non- // repeating element. #include <bits/stdc++.h> using namespace std; int firstNonRepeating(int arr[], int n) { ????// Insert all array elements in hash ????// table ????unordered_map<int, int> mp; ????for (int i = 0; i < n; i++) ????????mp[arr[i]]++; ????// Traverse array again and return ????// first element with count 1\. ????for (int i = 0; i < n; i++) ????????if (mp[arr[i]] == 1) ????????????return arr[i]; ????return -1; } // Driver code int main() { ????int arr[] = { 9, 4, 9, 6, 7, 4 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << firstNonRepeating(arr, n); ????return 0; } ``` ## Java ```java // Efficient Java program to find first non- // repeating element. import java.util.*; class GFG { ????static int firstNonRepeating(int arr[], int n) ????{ ????????// Insert all array elements in hash ????????// table ????????Map<Integer, Integer> m = new HashMap<>(); ????????for (int i = 0; i < n; i++) { ????????????if (m.containsKey(arr[i])) { ????????????????m.put(arr[i], m.get(arr[i]) + 1); ????????????} ????????????else { ????????????????m.put(arr[i], 1); ????????????} ????????} ????????// Traverse array again and return ????????// first element with count 1\. ????????for (int i = 0; i < n; i++) ????????????if (m.get(arr[i]) == 1) ????????????????return arr[i]; ????????return -1; ????} ????// Driver code ????public static void main(String[] args) ????{ ????????int arr[] = { 9, 4, 9, 6, 7, 4 }; ????????int n = arr.length; ????????System.out.println(firstNonRepeating(arr, n)); ????} } // This code contributed by Rajput-Ji ``` ## Python3 ```py # Efficient Python3 program to find first? # non-repeating element. from collections import defaultdict def firstNonRepeating(arr, n): ????mp = defaultdict(lambda:0) ????# Insert all array elements in hash table? ????for i in range(n): ????????mp[arr[i]] += 1 ????# Traverse array again and return? ????# first element with count 1.? ????for i in range(n): ????????if mp[arr[i]] == 1: ????????????return arr[i] ????return -1 # Driver Code arr = [9, 4, 9, 6, 7, 4] n = len(arr) print(firstNonRepeating(arr, n))? # This code is contributed by Shrikant13 ``` ## C# ``` // Efficient C# program to find first non- // repeating element. using System; using System.Collections.Generic; class GFG { ????static int firstNonRepeating(int[] arr, int n) ????{ ????????// Insert all array elements in hash ????????// table ????????Dictionary<int, int> m = new Dictionary<int, int>(); ????????for (int i = 0; i < n; i++) { ????????????if (m.ContainsKey(arr[i])) { ????????????????var val = m[arr[i]]; ????????????????m.Remove(arr[i]); ????????????????m.Add(arr[i], val + 1); ????????????} ????????????else { ????????????????m.Add(arr[i], 1); ????????????} ????????} ????????// Traverse array again and return ????????// first element with count 1\. ????????for (int i = 0; i < n; i++) ????????????if (m[arr[i]] == 1) ????????????????return arr[i]; ????????return -1; ????} ????// Driver code ????public static void Main(String[] args) ????{ ????????int[] arr = { 9, 4, 9, 6, 7, 4 }; ????????int n = arr.Length; ????????Console.WriteLine(firstNonRepeating(arr, n)); ????} } // This code has been contributed by 29AjayKumar ``` **輸出**： ``` 6 ``` **時間復雜度**：`O(n)` **輔助空間**：`O(n)` **進一步優化**：如果數組有很多重復項，我們還可以使用哈希表（其中值是[對](https://www.geeksforgeeks.org/pair-in-cpp-stl/)）將索引存儲在哈希表中。現在，我們只需要遍歷哈希表中的鍵（不是完整的數組）即可找到第一個非重復的鍵。 **打印所有非重復元素**： ## C++ ``` // Efficient CPP program to print all non- // repeating elements. #include <bits/stdc++.h> using namespace std; void firstNonRepeating(int arr[], int n) { ????// Insert all array elements in hash ????// table ????unordered_map<int, int> mp; ????for (int i = 0; i < n; i++) ????????mp[arr[i]]++; ????// Traverse through map only and ????for (auto x : mp) ????????if (x.second == 1) ????????????cout << x.first << " "; } // Driver code int main() { ????int arr[] = { 9, 4, 9, 6, 7, 4 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????firstNonRepeating(arr, n); ????return 0; } ``` ## Java ```java // Efficient Java program to print all non- // repeating elements. import java.util.*; class GFG { ????static void firstNonRepeating(int arr[], int n) ????{ ????????// Insert all array elements in hash ????????// table ????????Map<Integer, Integer> m = new HashMap<>(); ????????for (int i = 0; i < n; i++) { ????????????if (m.containsKey(arr[i])) { ????????????????m.put(arr[i], m.get(arr[i]) + 1); ????????????} ????????????else { ????????????????m.put(arr[i], 1); ????????????} ????????} ????????// Traverse through map only and ????????// using for-each loop for iteration over Map.entrySet() ????????for (Map.Entry<Integer, Integer> x : m.entrySet()) ????????????if (x.getValue() == 1) ????????????????System.out.print(x.getKey() + " "); ????} ????// Driver code ????public static void main(String[] args) ????{ ????????int arr[] = { 9, 4, 9, 6, 7, 4 }; ????????int n = arr.length; ????????firstNonRepeating(arr, n); ????} } // This code has been contributed by 29AjayKumar ``` ## Python3 ```py # Efficient Python program to print all non- # repeating elements. def firstNonRepeating(arr, n): ????# Insert all array elements in hash ????# table ????mp={} ????for i in range(n): ????????if arr[i] not in mp: ????????????mp[arr[i]]=0 ????????mp[arr[i]]+=1 ????# Traverse through map only and ????for x in mp: ????????if (mp[x]== 1): ????????????print(x,end=" ") # Driver code arr = [ 9, 4, 9, 6, 7, 4 ] n = len(arr) firstNonRepeating(arr, n) # This code is contributed by shivanisinghss2110 ``` ## C# ``` // Efficient C# program to print all non- // repeating elements. using System; using System.Collections.Generic; class GFG { ????static void firstNonRepeating(int[] arr, int n) ????{ ????????// Insert all array elements in hash ????????// table ????????Dictionary<int, int> m = new Dictionary<int, int>(); ????????for (int i = 0; i < n; i++) { ????????????if (m.ContainsKey(arr[i])) { ????????????????var val = m[arr[i]]; ????????????????m.Remove(arr[i]); ????????????????m.Add(arr[i], val + 1); ????????????} ????????????else { ????????????????m.Add(arr[i], 1); ????????????} ????????} ????????// Traverse through map only and ????????// using for-each loop for iteration over Map.entrySet() ????????foreach(KeyValuePair<int, int> x in m) ????????{ ????????????if (x.Value == 1) { ????????????????Console.Write(x.Key + " "); ????????????} ????????} ????} ????// Driver code ????public static void Main(String[] args) ????{ ????????int[] arr = { 9, 4, 9, 6, 7, 4 }; ????????int n = arr.Length; ????????firstNonRepeating(arr, n); ????} } /* This code contributed by PrinciRaj1992 */ ``` **輸出**： ``` 7 6 ``` * * * * * *