Пропущенные элементы в массиве

Есть очень старая задачка, которую часто задавали и задают на собеседованиях. Задавали её и мне, причем не один раз, задавал я и, тоже не один раз.

Формулировка: есть массив чисел длины 99 (ну или n - 1), в котором находятся числа от 1 до 100 (соответственно до n) в произвольном порядке, все по одному разу, кроме одного. Это одно отсутствующее число и надо найти.

Решается она не очень сложно, и довольно часто у кандидатов получается её решить (обычно с подсказками). Ну вы же знаете решение: считаем сумму элементов в массиве и вычитаем её из суммы элементов от 1 до n (которую можно посчитать по формуле n * (n + 1) / 2 или во время обхода массива). Ну или вместо сложения используем операцию исключающего или (xor) для элементов массива и чисел от 1 до n.

Есть расширенная версия этой задачи: теперь таких чисел два. В принципе, тоже не сложно. Раз чисел два, то нужна дополнительная информация, знания только о разности сумм недостаточно. Ну что же, можно считать произведение или сумму квадратов и решить квадратное уравнение.

Но что делать, если таких чисел m?

Недавно наша команда собеседовала очередного кандидата. Мой коллега задал эту задачу, в собеседовании организовалась пауза, и от нечего делать я решил подумать :) И придумал еще одно решение этой задачи. Для одного числа мой алгоритм имеет линейную сложность (хотя и не в один проход, как работают вышеописанные алгоритмы). Но зато его можно без проблем обобщить для общего случаю с отсутствующими m числами (время работы будет О(n * lg(m))). На форумах его не встречал, потому и публикую :)

В данном решении я использовал идею сортировки Хоара (она же быстрая, она же quicksort). Алгоритм быстрой сортировки сам по себе очень интересен, плюс имеет несколько любопытных приложений. Например, с помощью модификации quicksort можно находить порядковые статистики в массиве за линейное время. Похожую идею применил и я.

Рассмотрим случай одного отсутствующего элемента и массива длины 99. С помощью одного шага быстрой сортировки разобьем массив на два подмассива относительно среднего элемента (1 + 100) / 2 = 50. Посмотрим на длины этих подмассивов. В первом подмассиве находятся числа от 1 до 50, и если его длина равна 50, значит отсутствующее число находится во втором подмассиве. Если 49 - то в нем самом. Рекурсивно продолжаем алгоритм для той части, где находится пропущенное число. Время работы равно n + n/2 + n/4 + ... = 2n (шаг разбиения происходит за n). Причем в данном случае мы достаточно хорошо знаем медиану в массиве, поэтому массив разбивается на равные части с точностью до 1 (количества пропущенных элементов). Алгоритм легко обобщить и для m пропущенных элементов.

Ниже привожу Java реализацию обобщенного алгоритма:

public static int[] getMissing(final int[] a, final int missing) {
    return getMissing(a, 0, a.length - 1, 1, a.length + missing);
}

private static int[] getMissing(final int[] a, 
                                final int from, final int to,
                                final int minValue, final int maxValue) {

    if (to - from == maxValue - minValue) {
        return new int[0];
    }
    final int avg = (minValue + maxValue) / 2;
    final int avgIndex = split(a, from, to, avg);
    if (avgIndex > to) {
        return merge(
                getMissing(a, from, to, minValue, avg),
                getSequence(avg + 1, maxValue)
        );
    }
    if (avgIndex < from) {
        return merge(
                getSequence(minValue, avg),
                getMissing(a, from, to, avg + 1, maxValue)
        );
    }
    return merge(
            getMissing(a, from, avgIndex, minValue, avg),
            getMissing(a, avgIndex + 1, to, avg + 1, maxValue)
    );
}

private static int[] getSequence(final int min, final int max) {
    final int[] result = new int[max - min + 1];
    for (int v = min; v <= max; v++) {
        result[v - min] = v;
    }
    return result;
}

private static int[] merge(final int[] a, final int[] b) {
    final int[] result = new int[a.length + b.length];
    System.arraycopy(a, 0, result, 0, a.length);
    System.arraycopy(b, 0, result, a.length, b.length);
    return result;
}

public static int split(final int[] a, final int from, final int to, 
                        final int value) {
    int i = from;
    int j = to;
    do {
        while (a[i] <= value) {
            i++;
            if (i > to) {
                return i;
            }
        }
        while (a[j] > value) {
            j--;
            if (j < from) {
                return j;
            }
        }
        if (i <= j) {
            swap(a, i, j);
            i++;
            j--;
        }
    } while (i <= j);
    return j;
}

public static void swap(final int[] a, final int i, final int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}