在整數數組中找到第一個重復元素 · GeeksForGeeks 中文系列教程

# 在整數數組中找到第一個重復元素 > 原文： [https://www.geeksforgeeks.org/find-first-repeating-element-array-integers/](https://www.geeksforgeeks.org/find-first-repeating-element-array-integers/) 給定一個整數數組，在其中找到第一個重復元素。我們需要找到多次出現并且第一次出現的索引最小的元素。 **示例**： ``` Input: arr[] = {10, 5, 3, 4, 3, 5, 6} Output: 5 [5 is the first element that repeats] Input: arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10} Output: 6 [6 is the first element that repeats] ``` **簡單解決方案**是使用兩個嵌套循環。外循環一個接一個地選擇一個元素，內循環檢查該元素是否重復。找到重復的元素后，我們將中斷循環并打印該元素。該解決方案的時間復雜度為 `O(n^2)` 我們可以**使用排序**解決 O（nLogn）時間的問題。以下是詳細步驟。 1）將給定數組復制到輔助數組 temp []。 2）使用 O（nLogn）時間排序算法對臨時數組進行排序。 3）從左到右掃描輸入數組。對于每個元素，[使用二分搜索](https://www.geeksforgeeks.org/count-number-of-occurrences-in-a-sorted-array/)在 temp []中計算其出現次數。一旦發現一個元素出現多次，我們將返回該元素。此步驟可以在 O（nLogn）時間完成。我們可以**使用[散列](http://geeksquiz.com/hashing-set-1-introduction/)** 來平均解決`O(n)`時間。這個想法是從右到左遍歷給定的數組，并在我們找到在右側訪問過的元素時更新最小索引。感謝 Mohammad Shahid 提出了此解決方案。以下是此想法的實現。 ## C++ ```cpp /* C++ program to find first repeating element in arr[] */ #include<bits/stdc++.h> using namespace std; // This function prints the first repeating element in arr[] void printFirstRepeating(int arr[], int n) { ????// Initialize index of first repeating element ????int min = -1; ????// Creates an empty hashset ????set<int> myset; ????// Traverse the input array from right to left ????for (int i = n - 1; i >= 0; i--) ????{ ????????// If element is already in hash set, update min ????????if (myset.find(arr[i]) != myset.end()) ????????????min = i; ????????else?? // Else add element to hash set ????????????myset.insert(arr[i]); ????} ????// Print the result ????if (min != -1) ????????cout << "The first repeating element is " << arr[min]; ????else ????????cout << "There are no repeating elements"; } // Driver method to test above method int main() { ????int arr[] = {10, 5, 3, 4, 3, 5, 6}; ????int n = sizeof(arr) / sizeof(arr[0]); ????printFirstRepeating(arr, n); } //This article is contributed by Chhavi ``` ## Java ```java /* Java program to find first repeating element in arr[] */ import java.util.*; class Main { ????// This function prints the first repeating element in arr[] ????static void printFirstRepeating(int arr[]) ????{ ????????// Initialize index of first repeating element ????????int min = -1; ????????// Creates an empty hashset ????????HashSet<Integer> set = new HashSet<>(); ????????// Traverse the input array from right to left ????????for (int i=arr.length-1; i>=0; i--) ????????{ ????????????// If element is already in hash set, update min ????????????if (set.contains(arr[i])) ????????????????min = i; ????????????else?? // Else add element to hash set ????????????????set.add(arr[i]); ????????} ????????// Print the result ????????if (min != -1) ??????????System.out.println("The first repeating element is " + arr[min]); ????????else ??????????System.out.println("There are no repeating elements"); ????} ????// Driver method to test above method ????public static void main (String[] args) throws java.lang.Exception ????{ ????????int arr[] = {10, 5, 3, 4, 3, 5, 6}; ????????printFirstRepeating(arr); ????} } ``` ## Python3 ```py # Python3 program to find first repeating # element in arr[]? # This function prints the first repeating? # element in arr[] def printFirstRepeating(arr, n): ????# Initialize index of first repeating element ????Min = -1 ????# Creates an empty hashset ????myset = dict() ????# Traverse the input array from right to left ????for i in range(n - 1, -1, -1): ????????# If element is already in hash set, ????????# update Min ????????if arr[i] in myset.keys(): ????????????Min = i ????????else: # Else add element to hash set ????????????myset[arr[i]] = 1 ????# Print the result ????if (Min != -1): ????????print("The first repeating element is",? ??????????????????????????????????????arr[Min]) ????else: ????????print("There are no repeating elements") # Driver Code arr = [10, 5, 3, 4, 3, 5, 6] n = len(arr) printFirstRepeating(arr, n) # This code is contributed by Mohit kumar 29 ``` ## C# ```cs using System; using System.Collections.Generic; /* C# program to find first repeating element in arr[] */ public class GFG { ????// This function prints the first repeating element in arr[]? ????public static void printFirstRepeating(int[] arr) ????{ ????????// Initialize index of first repeating element? ????????int min = -1; ????????// Creates an empty hashset? ????????HashSet<int> set = new HashSet<int>(); ????????// Traverse the input array from right to left? ????????for (int i = arr.Length - 1; i >= 0; i--) ????????{ ????????????// If element is already in hash set, update min? ????????????if (set.Contains(arr[i])) ????????????{ ????????????????min = i; ????????????} ????????????else // Else add element to hash set ????????????{ ????????????????set.Add(arr[i]); ????????????} ????????} ????????// Print the result? ????????if (min != -1) ????????{ ??????????Console.WriteLine("The first repeating element is " + arr[min]); ????????} ????????else ????????{ ??????????Console.WriteLine("There are no repeating elements"); ????????} ????} ????// Driver method to test above method? ????public static void Main(string[] args) ????{ ????????int[] arr = new int[] {10, 5, 3, 4, 3, 5, 6}; ????????printFirstRepeating(arr); ????} } // This code is contributed by Shrikant13 ``` 輸出： ``` The first repeating element is 5 ```