Find the minimum element missing from sequence of non-negative integers

I need to find the minimum missing element from a sequence of non-negative integers.

ex: I have: 0 5 10 4 3 1

The missing element is 2.

开发者_如何学C

In above sequence missing elements are 2 6 7 8 9 . The minimum among them is 2 so answer is 2.

Brute force . I will sort the sequence and get the minimum element in nlogn .I am looking for better solution. Any help ?

---

In ISO C99:

unsigned least_absent(unsigned seq_sz, unsigned seq[seq_sz])
{
   bool tab[seq_sz];
   memset(tab, 0, sizeof(tab));
   for(unsigned i=0; i<seq_sz; i++)
      if(seq[i] < seq_sz)
         tab[seq[i]] = true;
   for(unsigned i=0; i<seq_sz; i++)
      if(!tab[i])
         return i;
   return seq_sz;
}

This is O(n) time, O(n) memory.

---

Can be done in O(n) with a hash table, which means O(n) additional memory:

1. Insert the numbers to a hash table, done in O(n).
2. Go from zero to the list's maximum, and check whether the number exists. The first number that does not exist is the answer. This is also done in O(n).

---

list = sort(list)
last_element = list[0]
for(i = 1; i < list.size; ++i){
   if(list[i] - last_element > 1) 
      return last_element + 1 // return the next number after last_element
   last_element = list[i]
}
return -1 // return -1 if unable to find a number

---

This solution is O(n) space and time complexity.

def solution(A):
    #Python 3.6

    a = set() #to store positive numbers in the given array
    b = set() #to store missing positive numbers in the given array

    for item in A:
        if item<=0:
            continue
        a.add(item)
        if item in b:
            b.remove(item)
        if item + 1 not in a:
            b.add(item+1)

    #if all numbers are negative in the given array
    if len(a) == 0:
        return 1

    #if 1 is not in the given array, 1 is the answer
    if 1 not in a:
        return 1

    return min(b)

---

Pseudocode:

for(int i = 0 ; i < Int.MAX ; i++)
{
   if(i is not in list)
   {
       return i
    }
}

Of course it may be possible to optimise this, but as an initial draft, in order to get your tests passing (you do have tests, right), its a very simple solution, which will give you confidence taht your tests are correct, freeing you up to optimise if needed.

---

No need for sorting.

1. Go over the list and find the 2 smallest valuse, which the difference between them is bigger than 1. (O(N)).

2. Print the (least value was found)+1.

---

Simplest approach I can think of is to sort the list and then look through it for the first gap.

I'm not sure there's anything much simpler. Even if you parse the list somehow without actually sorting it you're going to need to keep track of the gaps you've found along the way and then eliminate them as you go. I think it's probably logically equivalent to a sort algorithm anyway. Could be wrong.

---

First sort the elements. Then start finding the numbers in your sequence like:

for (int i=0; i<numbers.length; i++) {
   if (numbers[i] != i ) {
       System.out.println("Missing number is: " + i); break;
   }
}

---

Pseudocode :

a is the array
s is a sorted set (examples : a binary search tree, or a red/black tree)

insert 0 in s
for each v in a
  remove v from s
  insert v+1 in s

result is min(s)

---

1. Sort the array (O(NlogN) worst-case for mergesort)
2. Loop from the beginning, until a difference of more than 1 between two adjacent elements is encountered. (O(N) worst-case)

---

If you know there are no repeated elements you can do in O(N log N) time with O(1) memory:

You do a binary search to find the answer: initially you know the answer is between 0 and N-1, for each step, you count how many numbers are less than k (k the middle element of the binary search segment), if this number is equal to k, then that part of the sequence is complete, so you need to search the upper part, otherwise you need to search the lower part.

---

Improving some of the ideas (@Faisal Feroz, @slacker, @dahunter, @user453201): During the pass on the values list (Sorting, or inserting the values to hash/ lookup table), save the minimum. Then, in order to find the missing element, start from this minimum instead of 0. Small improvement, but it's still better.