查找 int[] 中的第一个唯一整数

Question

给定一个整数数组，我想 return 数组中的第一个唯一元素。我使用 List .contains() 方法检查 Integer 数组是否包含元素，该方法正确但效率不高（时间复杂度 O(N**2)），因为 List.contain() 循环比较每个元素的整个列表.

    List<Integer> list = new ArrayList<Integer>();
      int num = 0;
    for(int a: A){
        if(list.contains((Integer)a)){
            list.remove((Integer)a);
        }else{
          list.add(a); 
        }
       
    }

 
    num = !list.isEmpty()? (int) set.get(0): 0;
    return list.size()<1?-1:num;
}
//example input/output

int[] a = {1,2,6,1,6}

//I get the correct answer 2

做了我的研究，发现 HashSet 有 Contains 效率更高问题是，一旦我使用 HashSet（我也尝试过 Set），我就不会得到相同的结果。该函数应该 return int[]

中的第一个唯一元素

导入java.util.*;

    HashSet<Integer> set = new HashSet<Integer>();
      int num = 0;
    for(int a: A){
        if(set.contains(a)){
            set.remove((Integer)a);
        }else{
          set.add(a); 
        }
       
    }
 
    num = !set.isEmpty()? (int) set.iterator.next(): 0;
    return set.isEmpty()?-1:num;
}


  //example input/output

int[] a = {1,2,6,1,6}

// Should return 2 but get the wrong  answer 1

Answer 1

LinkedHashSet 应用于跟踪 第一个 唯一编号
需要另一个 Set 来在输入数组中保留 重复的 值，这可以使用 Set::add return 的事实来检测s false 当元素还没有被实际添加到集合中时。然后必须从输入集中删除重复数组，第一个剩余元素是 returned.

此外，return null / Integer 值可能比 -1 更好，后者更适合 returning 当找不到请求的值时，输入 array/list 中的索引。

话虽如此，解决方案可能如下所示：

public static Integer firstUnique(int ... arr) {
    Set<Integer> input = new LinkedHashSet<>();
    Set<Integer> duplicates = new HashSet<>();
    for (int x : arr) {
        if (!input.add(x)) {
            duplicates.add(x);
        }
    }
    input.removeAll(duplicates);
    return input.isEmpty() ? null : input.iterator().next();
}

测试：

System.out.println(firstUnique(1, 2, 6, 1, 4, 6)); // 2
System.out.println(firstUnique(1, 2, 6, 6, 1, 2)); // null

查找 int[] 中的第一个唯一整数

Finding the first unique integer in int[]

java

arrays

list

set

hashset