Find the Smallest Integer Not in a List

Вы можете сделать это за O (n) раз и O (1) дополнительного места, хотя скрытый фактор довольно велик. Это непрактичный способ решения проблемы, но, тем не менее, он может быть интересен.

Для каждого 64-битного целого числа без знака (в порядке возрастания) перебирайте список, пока не найдете целевое целое число или не дойдете до конца список. Если вы дойдете до конца списка, целевое целое число будет наименьшим целым числом, отсутствующим в списке. Если вы дойдете до конца 64-битных целых чисел, каждое 64-битное целое будет в списке.

Вот это как функция Python:

def smallest_missing_uint64(source_list):
    the_answer = None

    target = 0L
    while target < 2L**64:

        target_found = False
        for item in source_list:
            if item == target:
                target_found = True

        if not target_found and the_answer is None:
            the_answer = target

        target += 1L

    return the_answer

Эта функция намеренно неэффективна, чтобы сохранить ее O (n). Обратите особое внимание на то, что функция продолжает проверять целевые числа даже после того, как был найден ответ. Если функция вернулась, как только был найден ответ, количество запусков внешнего цикла будет ограничено размером ответа, который ограничен значением n. Это изменение сделало бы время выполнения O (n ^ 2), хотя оно было бы намного быстрее.

Мне нравится метод "угадай ноль". Если бы числа были случайными, очень вероятно, что ноль. Если «экзаменатор» установил неслучайный список, затем добавьте его и снова угадайте:

LowNum=0
i=0
do forever {
  if i == N then leave /* Processed entire array */
  if array[i] == LowNum {
     LowNum++
     i=0
     }
   else {
     i++
   }
}
display LowNum

Наихудший случай - n * N с n = N, но на практике n, скорее всего, будет небольшим числом (например, 1 )

Мы могли бы использовать хеш-таблицу для хранения чисел. Когда все числа будут выполнены, запустите счетчик от 0 до наименьшего. Достаточно хороший хэш будет хэшироваться и храниться в постоянное время и извлекаться в постоянное время.

for every i in X         // One scan Θ(1)
   hashtable.put(i, i);  // O(1)

low = 0;

while (hashtable.get(i) <> null)   // at most n+1 times
   low++;

print low;

Наихудший случай, если в массиве n элементов, а это {0, 1, ... n-1} , и в этом случае ответ будет получено в n , все еще сохраняя его O (n) .

Что ж, если в списке чисел пропущено только одно число, самый простой способ найти недостающее число - это сложить ряды и вычесть каждое значение в списке. Конечное значение - это пропущенное число.

Since the OP has now specified that the original list is held in RAM and that the computer has only, say, 1GB of memory, I'm going to go out on a limb and predict that the answer is zero.

1GB of RAM means the list can have at most 134,217,728 numbers in it. But there are 2⁶⁴ = 18,446,744,073,709,551,616 possible numbers. So the probability that zero is in the list is 1 in 137,438,953,472.

In contrast, my odds of being struck by lightning this year are 1 in 700,000. And my odds of getting hit by a meteorite are about 1 in 10 trillion. So I'm about ten times more likely to be written up in a scientific journal due to my untimely death by a celestial object than the answer not being zero.

To illustrate one of the pitfalls of O(N) thinking, here is an O(N) algorithm that uses O(1) space.

for i in [0..2^64):
  if i not in list: return i

print "no 64-bit integers are missing"

Here's a simple O(N) solution that uses O(N) space. I'm assuming that we are restricting the input list to non-negative numbers and that we want to find the first non-negative number that is not in the list.

1. Find the length of the list; lets say it is N.
2. Allocate an array of N booleans, initialized to all false.
3. For each number X in the list, if X is less than N, set the X'th element of the array to true.
4. Scan the array starting from index 0, looking for the first element that is false. If you find the first false at index I, then I is the answer. Otherwise (i.e. when all elements are true) the answer is N.

In practice, the "array of N booleans" would probably be encoded as a "bitmap" or "bitset" represented as a byte or int array. This typically uses less space (depending on the programming language) and allows the scan for the first false to be done more quickly.

This is how / why the algorithm works.

Suppose that the N numbers in the list are not distinct, or that one or more of them is greater than N. This means that there must be at least one number in the range 0 .. N - 1 that is not in the list. So the problem of find the smallest missing number must therefore reduce to the problem of finding the smallest missing number less than N. This means that we don't need to keep track of numbers that are greater or equal to N ... because they won't be the answer.

The alternative to the previous paragraph is that the list is a permutation of the numbers from 0 .. N - 1. In this case, step 3 sets all elements of the array to true, and step 4 tells us that the first "missing" number is N.

The computational complexity of the algorithm is O(N) with a relatively small constant of proportionality. It makes two linear passes through the list, or just one pass if the list length is known to start with. There is no need to represent the hold the entire list in memory, so the algorithm's asymptotic memory usage is just what is needed to represent the array of booleans; i.e. O(N) bits.

(By contrast, algorithms that rely on in-memory sorting or partitioning assume that you can represent the entire list in memory. In the form the question was asked, this would require O(N) 64-bit words.)

@Jorn comments that steps 1 through 3 are a variation on counting sort. In a sense he is right, but the differences are significant:

• A counting sort requires an array of (at least) Xmax - Xmin counters where Xmax is the largest number in the list and Xmin is the smallest number in the list. Each counter has to be able to represent N states; i.e. assuming a binary representation it has to have an integer type (at least) ceiling(log2(N)) bits.
• To determine the array size, a counting sort needs to make an initial pass through the list to determine Xmax and Xmin.
• The minimum worst-case space requirement is therefore ceiling(log2(N)) * (Xmax - Xmin) bits.

By contrast, the algorithm presented above simply requires N bits in the worst and best cases.

However, this analysis leads to the intuition that if the algorithm made an initial pass through the list looking for a zero (and counting the list elements if required), it would give a quicker answer using no space at all if it found the zero. It is definitely worth doing this if there is a high probability of finding at least one zero in the list. And this extra pass doesn't change the overall complexity.

EDIT: I've changed the description of the algorithm to use "array of booleans" since people apparently found my original description using bits and bitmaps to be confusing.

Молодцы, Муравьи Аасма! Я размышлял над ответом около 15 минут и независимо придумал ответ в том же духе, что и ваш:

#define SWAP(x,y) { numerictype_t tmp = x; x = y; y = tmp; }
int minNonNegativeNotInArr (numerictype_t * a, size_t n) {
    int m = n;
    for (int i = 0; i < m;) {
        if (a[i] >= m || a[i] < i || a[i] == a[a[i]]) {
            m--;
            SWAP (a[i], a[m]);
            continue;
        }
        if (a[i] > i) {
            SWAP (a[i], a[a[i]]);
            continue;
        }
        i++;
    }
    return m;
}

m представляет собой «текущий максимально возможный результат с учетом того, что я знаю о первых i входах, и ничего другого не предполагая. значения до входа в m-1 ».

Это значение m будет возвращено, только если (a [i], ..., a [m-1]) является перестановкой значений (i, ..., m-1). Таким образом, если a [i]> = m или если a [i]

Если это не так, но a [i]> i, тогда зная, что a [i]! = A [a [i]] мы знаем, что замена [i] на [a [i]] увеличит количество элементов на их собственном месте.