java - 查找具有最低第二次出现索引的第一个重复元素

Question

我正在尝试解决 CodeFights 上的一个名为 firstDuplicate 的问题，它指出 -

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example

For a = [2, 3, 3, 1, 5, 2], the output should be firstDuplicate(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, so the answer is 3.

For a = [2, 4, 3, 5, 1], the output should be firstDuplicate(a) = -1.

我的解决方案-

public class FirstDuplicate {
    private static HashMap<Integer, Integer> counts = new HashMap<>();

    private static void findSecondIndexFrom(int[] num, int n, int i) {
    // given an array, a starting index and a number, find second occurrence of that number beginning from next index
        for(int x = i; x < num.length; x++) {
            if(num[x] == n) {
              // second occurrence found - place in map and terminate
                counts.put(n, x);
                return;
            }
        }


    }

    private static int firstDuplicate(int[] a) {
        // for each element in loop, if it's not already in hashmap
        // find it's second occurrence in array and place number and index in map

        for(int i = 0; i < a.length; i++) {
            if(!counts.containsKey(a[i])) {
                findSecondIndexFrom(a, a[i], i+1);
            }
        }

        System.out.println(counts);
        // if map is empty - no duplicate elements, return -1
        if(counts.size() == 0) {
            return -1;
        }
        // else - get array of values from map, sort it, find lowest value and return corresponding key

        ArrayList<Integer> values = new ArrayList<>(counts.values());
        Collections.sort(values);
        int lowest = values.get(0);
        //System.out.println(lowest);
        for(Map.Entry<Integer, Integer> entries: counts.entrySet()) {
            if(entries.getValue() == lowest) {
                return entries.getKey();
            }
        }
     return -1;
    }

    public static void main(String[] args) {
         // int[] a = new int[]{2, 3, 3, 1, 5, 2};
         //int[] a = new int[]{2, 4, 3, 5, 1};
         //int[] a = new int[]{8, 4, 6, 2, 6, 4, 7, 9, 5, 8};
        //int[] a = new int[]{1, 1, 2, 2, 1};

        int[] a = new int[]{10, 6, 8, 4, 9, 1, 7, 2, 5, 3};
        System.out.println(firstDuplicate(a));
    }


}

此解决方案仅通过了 CodeFights 上 11 个测试用例中的大约 4 个。但是，我在我的 IDE 中手动执行了每一个测试用例，并且每一个都产生了正确的结果。

我不明白为什么这在 CodeFights 中不起作用。跟静态HashMap的使用有关系吗？

Answer 1

已编辑:由于可以一步完成添加和检查元素是否存在于 Set 中，因此代码可以简化为:

public static int findDuplicateWithLowestIndex(int... a){
Set<Integer> set = new HashSet<>();
   for(int num : a){
     if(!set.add(num)){
        return num;
       }
    }
return -1; 
}

帕特里克，你完全正确。