查找具有最低第二出现索引的第一个重复元素 [英] Find first duplicate element with lowest second occurrence index

问题描述

我正在尝试解决名为firstDuplicate的CodeFights上的问题-

I'm trying to solve a problem on CodeFights called firstDuplicate, that states -

给出一个数组a，其中只包含1到1之间的数字 a.length，找到第一个重复编号，第二个重复编号 发生次数具有最小索引.换句话说，如果还有更多 超过1个重复的数字，返回第二个数字 事件的索引比另一个事件的第二次出现的索引小 号.如果没有这样的元素，则返回-1.

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.

示例

对于a = [2、3、3、1、5、2]，输出应为firstDuplicate(a)= 3.

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

有2个重复项:数字2和3.第二次出现3 具有比第二次出现2小的索引，因此 答案是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.

对于a = [2、4、3、5、1]，输出应为firstDuplicate(a)= -1.

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中手动执行了每个测试用例，每个测试用例都能产生正确的结果.

This solution passes only for about 4 of the 11 test cases on CodeFights. However, I manually executed each one of the test cases in my IDE, and each one produces the right result.

我不知道为什么这在CodeFights中不起作用.它与静态HashMap的使用有关吗?

I can't figure out why this won't work in CodeFights. Does it have something to do with the use of the static HashMap?

推荐答案

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

Edited: Since adding and checking if element is present in Set can be done in one step, code can be simplified to:

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

您完全正确，帕特里克.

You're completly right Patrick.

这篇关于查找具有最低第二出现索引的第一个重复元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！