查找整数数组中第一个重复元素的程序

Question

查找整数数组中的第一个重复元素。
例如：

Input: array[] = {10, 7, 8, 1, 8, 7, 6}
Output: 7 [7 is the first element actually repeats]

Answer 1

简单的解决方案是使用两个循环。外循环将遍历循环，内循环将检查元素是否重复，但此解决方案的时间复杂度为 o(n^2)。

另一种解决方案是创建另一个数组并对其进行排序。从原始数组中选取元素并使用二进制搜索在排序数组中查找元素，但此解决方案的时间复杂度为 o(n^logn)。
我们能做得更好吗？
是的，我们可以从右到左迭代并使用HashSet来跟踪 minimumIndex

用 -1 初始化 minimumIndex * 从右到左迭代输入数组 * 如果元素已经存在于 Hashset 中，则更新 minimumIndex *否则将元素添加到集合中
一旦我们完成了迭代，我们最终会得到 minimumIndex
查找整数数组中第一个重复元素的程序

MaximumOccurringCharacterMain.java

package org.arpit.java2blog;
/* Java program to find first repeating element in arr[] */
import java.util.*; 

public class FirstRepatingElementMain 
{ 
    // This function prints the first repeating element in arr[] 
    static int getFirstRepeatingElementArray(int array[]) 
    { 
        // Initialize index of first repeating element 
        int minimumIndex = -1; 

        // Creates an empty hashset 
        HashSet<Integer> set = new HashSet<>(); 

        // Iterate over the input array from right to left 
        for (int i=array.length-1; i>=0; i--) 
        { 
            // If set contains the element, update minimum index 
            if (set.contains(array[i])) 
                minimumIndex = i; 

            else   // Else add element to hash set 
                set.add(array[i]); 
        } 
        return minimumIndex;
    } 

    public static void main (String[] args) throws java.lang.Exception 
    { 
        int array[] = {10, 7, 8, 1, 8, 7, 6}; 
        int min=getFirstRepeatingElementArray(array); 
        // Print the result 
        if (min != -1) 
            System.out.println("The first repeating element in array is " + array[min]); 
        else
            System.out.println("There are no repeating elements"); 
    } 
} 

当你运行上面的程序时，你会得到以下输出：

The first repeating element in array is 7