HashMap with Integers long time

Question

I have an array of numbers from 0 to the length of array, except that some number is missing and I have to find it.

public static Integer findNumber(Integer[] array){
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(Integer number : array){
        map.put(number, 1);
    }
    for(Integer i=0; i<array.length; i++){
        if(map.get(i)==null)
            return i;
    }
    return -1;
}

I thought this was gonna be a good solution, but putting takes a really long time, sorting solution with counting duplicates is a lot faster, and I have no idea why. Hash for Integer is that Integer itself, so there's not even time lost on counting hash, and no iterating with equals (that depends on numbers, I picked an example with only a single duplicate). I feel like I'm missing something obvious here. I tried specifying initial capacity and load factor, but it only makes things worse. Can I optimize this somehow?

It's putting that takes a lot of time, not iterating over to find solution, putting is like 95% of the time of execution.

I thought so too, I started with primitive ints then changed for Integer, didn't change anything at all. I think even if it makes things slower, it doesn't make them that much slower. — Haratino, Jul 11 '16 at 09:23
Possible duplicate of [Quickest way to find missing number in an array of numbers](http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers) — m69's been on strike for years, Jul 11 '16 at 15:47

kkonrad · Answer 1 · 2018-09-21T08:56:48.733

4

You can go simpler and faster way: sum integers in array and then subtract it from (it is sum of number from 1 to n). Remaining value is number that it is missing.

One note: if your n can be any non-negative Integer, you would need to perform all computation on Long type so that you don't run into overflow. Final number is guaranteed to be Integer, but multiplication can be outside Integer range.

edited Sep 21 '18 at 08:56

answered Jul 11 '16 at 09:38

kkonrad

1,262
13
32

Like a lot of these puzzles it's a mathematical trick they are looking for, not a programming one. +1 – Peter Lawrey Jul 11 '16 at 10:08

score 0 · Answer 2 · answered Jul 11 '16 at 09:21

0

instead of Map, you could use an array of (primitive) boolean. in the first loop, instead of putting 1 you flip the array's cell to true: boolArray[number] = true;

after that, loop on the array and find the missing number

answered Jul 11 '16 at 09:21

Sharon Ben Asher

13,849
5
33
47

yes, that's actually the idea I wanted to achieve with a map, and I thought map was gonna be as fast as this, maybe just a little slower, because it does almost the same thing under the hood, let's say I put number 20 in a map, it counts hash which is the same and then it does internalArray[20]=1, which is like boolArray[number]=true. – Haratino Jul 11 '16 at 09:29
the difference is that after you fill the bool array you iterate on it instead of on the number array, see my other answer - iterate on the map's values to search for the null – Sharon Ben Asher Jul 11 '16 at 09:32

score 0 · Answer 3 · answered Jul 11 '16 at 09:30

0

if you insist on using map: the second loop should not go over the array, but rather over the map's values, searching for the null one:

map.values().stream().filter(v -> v == null).findFirst();

answered Jul 11 '16 at 09:30

Sharon Ben Asher

13,849
5
33
47

score -1 · Answer 4 · answered Jul 11 '16 at 09:20

-1

I think there's a more simple solution. Try this :

public static Integer findNumber(Integer[] array){

     for(Integer i=0; i<array.length; i++){
         if(i != array[i])
             return i;
     }
     return -1;
}

Hope that will help you.

answered Jul 11 '16 at 09:20

mrk

1
1

I don't think that will work, example : `array={2,1,3}` the missing number should be 0 but your code will return 2 – niceman Jul 11 '16 at 09:21
This code neither handles duplicate numbers or unsorted arrays. – Tom Jul 11 '16 at 09:27
Right niceman, I didn't understand very well the problem. But after some research I think what he's looking for is (mathematically)answered here [http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers](http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers) – mrk Jul 11 '16 at 09:48

HashMap with Integers long time

4 Answers4