在整数数组中找到第一个重复元素
原文： 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)时间的问题。 以下是详细步骤。
-
将给定数组复制到辅助数组
temp[]。 -
使用
O(nLogn)时间排序算法对临时数组进行排序。 -
从左到右扫描输入数组。 对于每个元素，使用二分搜索在
temp[]中计算其出现次数。 一旦发现一个元素出现多次，我们将返回该元素。 此步骤可以在O(nLogn)时间完成。
我们可以使用散列来平均解决O(n)时间。 这个想法是从右到左遍历给定的数组，并在我们找到在右侧访问过的元素时更新最小索引。 感谢 Mohammad Shahid 提出了此解决方案。
以下是此想法的实现。
C++
/* 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 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
# 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#
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
版权属于：月萌API www.moonapi.com，转载请注明出处
