How could we get an unique element from a double array, using a map‽

Question

I am currently solving the following programming exercise: Find the unique number The statement is:

There is an array with some numbers. All numbers are equal except for one. Try to find it!

Kata.findUniq(new double[]{ 1, 1, 1, 2, 1, 1 }); // => 2 Kata.findUniq(new double[]{ 0, 0, 0.55, 0, 0 }); // => 0.55

It’s guaranteed that array contains more than 3 numbers.

The tests contain some very huge arrays, so think about performance.

First my thought was to get all elements frequencies as a map, and then return the key which frequency value is just 1.

I wrote the following:

import java.util.stream.*;

 public class Kata {
    public static double findUniq(double arr[]) {

      Map<Double, Long> frequencies = Arrays.stream(arr)
        .collect(Collectors.groupingBy(n -> n, Collectors.counting()));

      System.out.println("Map: "+map);

    }
}

So it outputs:

./src/main/java/Kata.java:8: error: method collect in interface DoubleStream cannot be applied to given types;
        .collect(Collectors.groupingBy(n -> n, Collectors.counting()));
        ^
  required: Supplier<R>,ObjDoubleConsumer<R>,BiConsumer<R,R>
  found: Collector<Object,CAP#1,Map<Object,Long>>
  reason: cannot infer type-variable(s) R
    (actual and formal argument lists differ in length)
  where R is a type-variable:
    R extends Object declared in method <R>collect(Supplier<R>,ObjDoubleConsumer<R>,BiConsumer<R,R>)
  where CAP#1 is a fresh type-variable:
    CAP#1 extends Object from capture of ?
./src/main/java/Kata.java:10: error: cannot find symbol
      System.out.println("Map: "+map);
                                 ^
  symbol:   variable map
  location: class Kata
2 errors

I suppose the way to solve this issue is to understand:

required: Supplier<R>,ObjDoubleConsumer<R>,BiConsumer<R,R>
  found: Collector<Object,CAP#1,Map<Object,Long>>

I do know it expects: Supplier<R>,ObjDoubleConsumer<R>,BiConsumer<R,R> and I am writting: Collector<Object,CAP#1,Map<Object,Long>> but what does it mean? How could we fix it? Why is it generated?

Then I tried a second approach: use a HashSet to get all distinct doubles, then remove the one which is not unique, and return the unique one, which is stored in the HashSet.

import java.util.*;
import java.util.stream.*;

 public class Kata {
    public static double findUniq(double arr[]) {
      System.out.println("\nOriginal array: "+Arrays.toString(arr));

      Set<Double> unique = new HashSet<Double>();
      double repeated = Double.MIN_VALUE;

      for(int i = 0; i < arr.length; i++){
        if(repeated != arr[i] && !unique.add(arr[i])){
          repeated = arr[i];
        }
      }
      unique.remove(repeated);
      System.out.println("Set: "+Arrays.toString(unique.toArray()));
      return (double)unique.toArray()[0];
    }
}

My question is, how could we achieve to return the unique element, using the first approach, counting frequencies with a map and then returning the key which value is 1‽.

I have also read:

Java Hashmap: How to get key from value? How to get unique items from an array?

upvote for the question mark and exclamation at the end of the title. — aydinugur, Nov 17 '19 at 09:54
Here's the method collect() of DoubleStrem that you're trying to call: https://docs.oracle.com/javase/8/docs/api/java/util/stream/DoubleStream.html#collect-java.util.function.Supplier-java.util.function.ObjDoubleConsumer-java.util.function.BiConsumer-. As you can see, it expects 3 arguments. But you only pass 1 argument. So that can't possibly compile. The collect() method you're using exists in the class Stream, but not in the class DoubleStream that you're using. Since this solution already requires boxing anyway, you could create a Stream using DoubleStream.boxed() — JB Nizet, Nov 17 '19 at 09:58
Obligatory comment: you're not caring about performance by boxing all the numbers and creating lots of map entries. You should rely on the fact that all numbers are equal except one, and that the array at least has 3 elements. If the two first elements are equal, then find the element that is different from the first one. If they are different, then use the value of the third one to know if the unique element is the first one or the second one. No boxing required, no collection required, as fast as it can be. — JB Nizet, Nov 17 '19 at 10:10

Sweeper · Accepted Answer · 2019-11-17T10:12:41.540

1

The compiler error occurs because the Collector that you are using does not work on DoubleStream - the specialised Stream type for primitive doubles. What you can do is to turn the DoubleStream into a Stream<Double> first, then apply the Collector:

Map<Double, Long> frequencies = Arrays.stream(arr)
        .boxed() // this is the key method to call
        .collect(Collectors.groupingBy(n -> n, Collectors.counting()));

Then you need to find the KVP with value 1, but maps aren't really meant for this though:

System.out.println("Map: "+ 
    frequencies.entrySet().stream()
        .filter(x -> x.getValue() == 1)
        .findFirst().get().getKey());

Note that there are much faster solutions than this. Keep in mind that exactly one double is different!

edited Nov 17 '19 at 10:12

answered Nov 17 '19 at 10:01

Sweeper

213,210
22
193
313

A much much better solution would consist in avoiding boxing and populating collections, and relying on the fact that all the numbers are equal except one. – JB Nizet Nov 17 '19 at 10:02
@JBNizet Yeah, but the point of the question is not to solve the challenge, so I'll leave it to the OP to figure that out. – Sweeper Nov 17 '19 at 10:11
I agree. My comment was more for the OP than for you. I've added a comment on the question. – JB Nizet Nov 17 '19 at 10:12

How could we get an unique element from a double array, using a map‽

1 Answers1