Алгоритм поиска наименьшего неотрицательного целого числа, которого нет в списке

Question

Учитывая список целых чисел, как мне лучше всего найти целое число, которое не в списке?

Список потенциально может быть очень большим, а целые числа могут быть большими (то есть BigIntegers, а не только 32-битными целыми числами).

Если есть какая-то разница, список «вероятно» отсортирован, то есть 99% времени он будет отсортирован, но я не могу полагаться на то, что сортировка будет всегда.

Редактировать -

Чтобы уточнить, учитывая список {0, 1, 3, 4, 7}, примерами приемлемых решений будут -2, 2, 8 и 10012, но я бы предпочел найти наименьшее, неотрицательное решение ( т.е. 2) если есть алгоритм, который может найти его без необходимости сортировки всего списка.

Answer 1

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

Если число имеет ограничения (например, max + 1 и min-1 могут переполниться), то вы можете использовать алгоритм сортировки, который хорошо работает с частично отсортированными данными . Затем просмотрите список и найдите первую пару чисел v_i и v_ {i + 1}, которые не являются последовательными. Возврат v_i + 1.

Чтобы получить наименьшее неотрицательное целое число (основываясь на правке в вопросе), вы можете:

• Сортировка списка с использованием частичной сортировки, как указано выше. Двоичный поиск в списке по 0. Перебирайте список по этому значению, пока не найдете «пробел» между двумя числами. Если вы дойдете до конца списка, верните последнее значение + 1.

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

Answer 2

Одним простым способом было бы перебрать список, чтобы получить наибольшее значение n, тогда вы знаете, что n+1 отсутствует в списке.

Edit:

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

Этот метод использует начало списка в качестве места для хранения меньших чисел, переменная startIndex отслеживает начало соответствующих чисел:

public static int GetSmallest(int[] items) {
    int startIndex = 0;
    int result = 0;
    int i = 0;
    while (i < items.Length) {
        if (items[i] == result) {
            result++;
            i = startIndex;
        } else {
            if (items[i] < result) {
                if (i != startIndex) {
                    int temp = items[startIndex];
                    items[startIndex] = items[i];
                    items[i] = temp;
                }
                startIndex++;
            }
            i++;
        }
    }
    return result;
}

Я провел тест производительности, в котором я создал списки с 100000 случайных чисел от 0 до 19999, что делает среднее наименьшее число около 150. При выполнении тестов (по 1000 списков тестов в каждом) метод нашел наименьшее число в несортированных списках в среднем за 8,2 мс, а в отсортированных списках - в среднем за 0,32 мс *

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

Answer 3

Я получил 100% как в правильности, так и в производительности, Вы должны использовать быструю сортировку, которая сложность N log (N) Вот, пожалуйста ...

    public int solution(int[] A) {
    if (A != null && A.length > 0) {
        quickSort(A, 0, A.length - 1);
    }

    int result = 1;
    if (A.length == 1 && A[0] < 0) {
        return result;
    }

    for (int i = 0; i < A.length; i++) {
        if (A[i] <= 0) {
            continue;
        }
        if (A[i] == result) {
            result++;
        } else if (A[i] < result) {
            continue;
        } else if (A[i] > result) {
            return result;
        }
    }

    return result;
}

private void quickSort(int[] numbers, int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high - low) / 2];

    while (i <= j) {
        while (numbers[i] < pivot) {
            i++;
        }
        while (numbers[j] > pivot) {
            j--;
        }

        if (i <= j) {
            exchange(numbers, i, j);
            i++;
            j--;
        }
    }
    // Recursion
    if (low < j)
        quickSort(numbers, low, j);
    if (i < high)
        quickSort(numbers, i, high);
}

private void exchange(int[] numbers, int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}

Answer 4

«вероятно, отсортировано» означает, что вы должны рассматривать его как полностью не отсортированный. Если, конечно, вы можете гарантировать, что это было отсортировано, это просто. Просто посмотрите на первый или последний элемент и сложите или вычтите 1.

Answer 5

Если он не отсортирован, вам придется выполнять линейный поиск по элементам, пока вы не найдете совпадение или не достигнете конца списка. Если вы можете гарантировать, что он отсортирован, вы всегда можете использовать метод массива BinarySearch или просто выполнить свой собственный двоичный поиск.

Или, как упоминал Джейсон, всегда есть возможность использовать Hashtable.

Answer 6

Предполагая, что это проблема, о которой я думаю:

У вас есть set из всех ints в диапазоне от 1 до n, но один из этих ints отсутствует. Скажите, какой из int отсутствует.

Это довольно простая задача, которую можно решить с помощью простых математических знаний. Известно, что сумма диапазона 1 .. n равна n(n+1) / 2. Итак, пусть W = n(n+1) / 2 и пусть Y = сумма чисел в вашем наборе. Целое число, отсутствующее в вашем наборе, X, будет тогда X = W - Y.

Примечание: ТАК необходимо поддерживать MathML

Если это не та проблема или если она носит более общий характер, то одно из других решений, вероятно, является правильным. Я просто не могу судить по этому вопросу, потому что он немного расплывчатый.

Редактировать: Ну, так как редактирование, я вижу, что мой ответ абсолютно неправильный. Тем не менее забавная математика.

Answer 7

Если вы не можете гарантировать, что он отсортирован, тогда у вас будет наилучшая временная эффективность O (N), так как вы должны смотреть на каждый элемент, чтобы убедиться, что ваш окончательный выбор не найден. Так что вопрос тогда:

1. Можно ли это сделать за O (N)?
2. Какова максимальная эффективность использования пространства?

Решение Криса Доггетта найти max и add 1 - это O (N) и экономия пространства (O (1) использования памяти)

Если вы хотите только, вероятно, лучший ответ, тогда это другой вопрос.

Answer 8

Есть несколько подходов:

• найдите самый большой int в списке и сохраните его в x. х + 1 не будет в списке. То же самое относится к использованию min () и x-1.

• Если N - размер списка, выделите массив типа int с размером (N+31)/32. Для каждого элемента в списке установите бит v&31 (где v - значение элемента) целого числа в индексе массива i/32. Игнорировать значения, где i/32 >= array.length. Теперь найдите первый элемент массива '! = 0xFFFFFFFF' (для 32-битных целых).

Answer 9

Вы ищете онлайновый алгоритм (поскольку вы говорите, что входной сигнал произвольно большой)? Если это так, взгляните на алгоритм Odds .

В противном случае, как уже предлагалось, хэшировать элементы ввода, поиска и включения / выключения логического набора (хэш-индексы в наборе).

Answer 10

Теоретически найдите максимальное значение и добавьте 1. Предполагая, что вы ограничены максимальным значением типа BigInteger, сортируйте список, если он не отсортирован, и ищите пробелы.