代码之家 › 专栏 › 技术社区 › George Galantsev

在Java中查找列表中具有重复项的唯一元素

unique arrays java

George Galantsev · 技术社区 · 8 年前

我们有一个整数(或其他对象)列表,如:

[0, 0, 1, 1, ... , 777777, ... , 999999, 999999]

Java代码:

List<Integer> ints = new LinkedList<Integer>();
for (int i = 0; i < 999999; i++) {
    ints.add(i); // add first value
    if (i!=777777){
        ints.add(i); // add duplicate value in not '5'
    }
}

我这样解决这个问题:

Integer unique = null;
while (true) {
    unique = ints.get(0);
    ints.remove(0);
    if (ints.contains(unique)) {
        ints.remove(ints.indexOf(unique));
    } else {
        break;
    }
}
System.out.println(unique);// 777777

使用ArrayList大约需要30毫秒,工作时间更长。问题是如何以最优(右/优雅/最快)的方式从该列表中获取一个唯一值(例如777777)。

7 回复 | 直到 8 年前

Eran 8 年前

由于您运行线性时间操作,例如 ints.contains(unique) 和 ints.indexOf(unique) O(n^2) 在最坏的情况下。

如果数字总是按顺序排序(如示例中所示),则可以在列表中的元素上迭代一次以查找元素 list.get(i) 这不等于 list.get(i-1) 和 list.get(i+1) . 这需要 O(n) .

如果数字不总是排序,您可以将其排序 O(nlogn) 然后像以前一样继续。

或者,您可以对这些数字迭代一次,计算每个数字的出现次数(您可以将计数存储在 HashMap ),并找到计数为1的数字。这需要 O(n) 无论输入列表是否排序。

Ricola 7 年前

除了 Set 如果您知道重复元素只出现,则由其他答案给出的解决方案两次 (或偶数次)并且只有 一个非重复 数字,您可以对所有值进行异或运算以找到唯一值。

public int findUnique(int[] nums) { // Or (List<Integer> nums), it works also
    int xor = 0;
    for(int i : nums){
        xor ^= i;
    }
    return xor;
}

此解决方案比其他解决方案更快、更短。

您也可以使用Java 8风格,但速度当然会较慢:

public int findUnique(int[] nums) {
    return Arrays.stream(nums)
            .reduce((acc,i) -> acc ^= i)
            .orElseThrow(IllegalArgumentException::new);
}

Abdullah Tellioglu 8 年前

你应该使用 哈希集 对于这个问题。

private void find(List<Integer> ints){
   HashSet<Integer> set = new HashSet<>();
   for(int i=0;i<ints.size();i++){
       if(set.contains(i)){
          set.remove(i);
       }else{
          set.add(i);
       }
   }
   Iterator<Integer> itr = set.iterator();
   if(itr.hasNext()){
      System.out.println("Unique value is :"+itr.next());
   }else{
      System.out.println("There is no duplicated value");
   }
}

这种方法仅适用于2个和1个计数列表项。如果您有3次相同的数字,这种方法会发现它是重复的。

Vishal Kawade 8 年前

首先获取唯一元素,然后使用collections api的频率方法获取重复的出现次数

Set<String> uniqueSet = new HashSet<String>(list);

for (String temp : uniqueSet) {
    if(Collections.frequency(list, temp)==1) {
      System.out.println(temp);
    }

}

这将从列表中返回唯一的元素。

Optional 8 年前

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;

public class FiindUnique {

    public static void main(String[] args) {
        System.out.println("Hello World");
        Collection<String> list = Arrays.asList("A", "B", "C", "D", "A", "B", "C");

        //solution 1
        List<String> distinctElements = list.stream().filter(name -> Collections.frequency(list, name) == 1).collect(Collectors.toList());
        System.out.println(distinctElements);

        //Solution 2

        List<String> distinctElements2 = list.stream()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
            .entrySet()
            .stream()
            .filter(e -> e.getValue() == 1)
            .map(e -> e.getKey())
            .collect(Collectors.toList());
         System.out.println(distinctElements2);
    }
}

Sameer 5 年前

通过进行二进制搜索来找到反转点,即在唯一数之前,偶数和奇数索引将具有相同的数,而在唯一数之后,奇数和偶数将具有相同的数,因此我们可以进行二进制搜索来找到反转点,时间复杂度将为log(N)

-1

Galg 8 年前

您是否假设数组已排序? 这可能会更快。

HashSet<Integer> s = new HashSet<Integer>();

for ( Integer i : ints){
    if ( s.contains(i)){
        s.remove(i); // remove dups
    }
    else{
        s.add(i); //add uniques
    }
}

for ( Integer unique: s){
// should contain one value
    System.out.println(unique);// 777777
}