Если мы предположим, что диапазон чисел всегда будет равен 2 ^ n (четная степень 2), то будет работать исключающее-или (как показано на другом плакате).Насколько это так, давайте докажем это:
Теория
Учитывая любой целочисленный диапазон на основе 0, в котором есть 2^n элементов с одним отсутствующим элементом, вы можете найти этот отсутствующий элемент просто путем xorобъединение известных значений для получения пропущенного числа.
Доказательство
Давайте рассмотрим n = 2. Для n = 2 мы можем представить 4 уникальных целых числа: 0, 1, 2, 3. Они имеют битовую комбинацию:
- 0 - 00
- 1 - 01
- 2 - 10
- 3 - 11
Теперь, если мы посмотрим, каждый бит установлен ровно дважды.Следовательно, поскольку оно установлено четное число раз, и исключающее число или будет давать число 0. Если пропущено одно число, исключающее число или выдаст число, которое при исключении или пропущенном числе приведет к0. Следовательно, пропущенный номер и полученный в результате эксклюзивный номер в точности совпадают.Если мы удалим 2, результирующее значение xor будет равно 10 (или 2).
Теперь давайте посмотрим на n + 1.Давайте назовем, сколько раз каждый бит установлен в n, x и сколько раз каждый бит установлен в n+1 y.Значение y будет равно y = x * 2, потому что есть x элементы с битом n+1, установленным в 0, и x элементы с битом n+1, установленным в 1. А так как 2xвсегда будет четным, n+1 всегда будет иметь каждый бит установленное четное количество раз.
Следовательно, поскольку n=2 работает, а n+1 работает, метод xor будет работать для всех значений n>=2.
Алгоритм для 0 основанных диапазонов
Это довольно просто.Он использует 2 * n бит памяти, поэтому для любого диапазона <= 32 будут работать 2 32-битных целых числа (без учета любой памяти, используемой дескриптором файла).И он делает один проход файла. </p>
long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
result = result ^ supplied;
}
return result;
Алгоритм произвольных основанных диапазонов
Этот алгоритм будет работать для диапазонов от любого начального числа до любого конечного числа, покаобщий диапазон равен 2 ^ n ... Это в основном переопределяет диапазон, чтобы иметь минимум в 0. Но это действительно требует 2 прохода через файл (первый, чтобы получить минимум, второй, чтобы вычислить отсутствующее целое число).
long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
if (supplied < offset) {
offset = supplied;
}
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
result = result ^ (supplied - offset);
}
return result + offset;
Произвольные диапазоны
Мы можем применить этот модифицированный метод к набору произвольных диапазонов, поскольку все диапазоны будут пересекать степень 2 ^ n как минимум один раз.Это работает, только если пропущен один бит.Требуется 2 прохода несортированного файла, но каждый раз он находит единственное пропущенное число:
long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
if (supplied < offset) {
offset = supplied;
}
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
n++;
result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
result = result ^ (n++);
}
return result + offset;
По существу, заново устанавливает диапазон около 0. Затем он подсчитывает количество несортированных значений для добавлениякак он вычисляет исключающее-или.Затем он добавляет 1 к количеству несортированных значений, чтобы позаботиться о пропущенном значении (подсчитать пропущенное).Затем продолжайте сохранять значение n, увеличивая его на 1 каждый раз, пока n не станет степенью 2. Затем результат возвращается к исходному основанию.Готово.
Вот алгоритм, который я тестировал в PHP (с использованием массива вместо файла, но с той же концепцией):
function find($array) {
$offset = min($array);
$n = 0;
$result = 0;
foreach ($array as $value) {
$result = $result ^ ($value - $offset);
$n++;
}
$n++; // This takes care of the missing value
while ($n == 1 || 0 != ($n & ($n - 1))) {
$result = $result ^ ($n++);
}
return $result + $offset;
}
Сжатие в массиве с любым диапазоном значений (я тестировалвключая отрицательные значения) с одним внутри этого диапазона, который отсутствует, он каждый раз находил правильное значение.
Другой подход
Поскольку мы можем использовать внешнюю сортировку, почему бы не просто проверить наличие пропуска?Если мы предположим, что файл отсортирован до запуска этого алгоритма:
long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
if (supplied != last + 1) {
return last + 1;
}
last = supplied;
}
// The range is contiguous, so what do we do here? Let's return last + 1:
return last + 1;