时间戳

首页 > 解决方案 > 在 int[] 中查找第一个唯一整数

java - 在 int[] 中查找第一个唯一整数

问题描述

给定一个整数数组，我想返回数组中的第一个唯一元素。我使用 A 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 包含更有效的内容问题是一旦我使用 HashSet（我也尝试过 Set），我不会得到相同的结果。该函数应返回 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

标签： javaarrayslistsethashset

解决方案

  1. LinkedHashSet应该使用维护插入顺序的方法来跟踪第 一个唯一编号
  2. 另一个Set是需要将重复值保留在输入数组中，这可以使用在元素尚未实际添加到集合时Set::add返回的事实来检测。false然后必须从输入集中删除重复数组并返回第一个剩余元素。

此外，当未找到请求的值时，返回null/Integer值可能更好，而不是-1更适合返回输入数组/列表中的索引。

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

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

推荐阅读