java - 首先使用java在数组中重复

Question

我正在尝试解决一个问题，我需要找到索引较低的重复数字。

例如，如果数组是{1,4,3,5,3,2,1}那么答案应该是 3，因为它的索引比下一个重复的整数 1 更小。

如果没有找到重复的数字则需要返回-1。我需要编写一个程序，以 o(n) 的时间复杂度来执行它。

我能够以 O(n^2) 概率求解它，但不知道如何以 O(n) 求解。另外我不明白如果没有找到重复的数字如何实现。请帮助我。我被困在这里了。

提前谢谢您。

到目前为止我的代码:

import java.util.ArrayList;
import java.util.Collections;

public class firstDuplicate
{
    //defining array
    public static void main(String args[]) 
    {
     int[] a1 = new int[] {2,3,3,1,5,2};

    //int[] a1 = new int[] {2,3,4,1,5,8};

    for(int i=0;i<a1.length; i++) 
    {
        System.out.println(a1[i]);
    }
    int counter =0;
    ArrayList<Integer> list1 = new ArrayList<>();


    for(int i =0; i<a1.length; i++) 
    {
        for(int j=i+1;j<a1.length; j++) 
        {
            if(a1[i]==a1[j])
            {
                counter =counter+1;
                System.out.println(j);
                list1.add(j);

            }
            else {
                int k =-1;
                System.out.println(k);
            }
        }


    }

    System.out.println("Printing ur numbers of repetation");
    System.out.printf("%d",counter);
    System.out.println("If printed ur answer is following");
    int k = Collections.min(list1);
    System.out.println(k);
    }
}

Answer 1

您可以像这样继续:

• 创建一个空 Set，然后对于输入数组中的每个元素，

• 检查元素是否已在集合中

  • 如果是，则在此处停止算法并返回当前元素作为结果
  • 如果否，则将当前元素添加到集合中，并继续处理数组中的下一个元素。