Зачем все усложнять? Вы просите целое число, которого нет в файле?

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

Нет никакого риска попасть в maxint или что-то еще, потому что, согласно правилам, нет ограничений на размер целого числа или числа, возвращаемого алгоритмом.

Это можно решить в очень небольшом объеме, используя вариант двоичного поиска.

1. Начните с допустимого диапазона чисел от 0 до 4294967295.

2. Рассчитайте среднюю точку.

3. Прокрутите файл, подсчитывая, сколько чисел было равно, меньше или больше среднего значения.

4. Если нет равных чисел, все готово. Число средней точки - это ответ.

5. В противном случае выберите диапазон, в котором было наименьшее количество номеров, и повторите действия, начиная с шага 2, с этим новым диапазоном.

Для этого потребуется до 32 линейных сканирований файла, но для хранения диапазона и счетчиков будет использовано только несколько байтов памяти.

По сути, это то же самое, что и решение Хеннинга, за исключением того, что он использует два бина вместо 16k.

РЕДАКТИРОВАТЬ Хорошо, это было не совсем продумано, поскольку предполагается, что целые числа в файле соответствуют некоторому статическому распределению. По-видимому, в этом нет необходимости, но даже тогда стоит попробовать следующее:

Существует ≈4,3 миллиарда 32-битных целых чисел. Мы не знаем, как они распределены в файле, но худший случай - это тот, у которого самая высокая энтропия Шеннона: равное распределение. В этом случае вероятность того, что какое-либо целое число не появится в файле, равна

( (2³²-1)/2³² )⁴ ⁰⁰⁰ ⁰⁰⁰ ⁰⁰⁰ ≈ .4

Чем ниже энтропия Шеннона, тем выше в среднем эта вероятность, но даже в этом наихудшем случае у нас есть 90% шанс найти не повторяющееся число после 5 предположений со случайными целыми числами. Просто создайте такие числа с помощью генератора псевдослучайных чисел, сохраните их в списке. Затем прочтите int после int и сравните со всеми своими догадками. Когда есть совпадение, удалите эту запись из списка. После того, как вы просмотрели весь файл, скорее всего, у вас останется более одного предположения. Воспользуйтесь любым из них. В редком (10% даже в худшем случае) событии, когда не остается никаких догадок, получите новый набор случайных целых чисел, возможно, на этот раз больше (10-> 99%).

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

Если у вас отсутствует одно целое число в диапазоне [0, 2 ^ x - 1], просто исключайте их все вместе. Например:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(Я знаю, что это не отвечает на вопрос точно, но это хороший ответ на очень похожий вопрос.)

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

Исходя из текущей формулировки исходного вопроса, самое простое решение:

Найдите максимальное значение в файле и добавьте к нему 1.

Используйте BitSet. 4 миллиарда целых чисел (при условии, что до 2 ^ 32 целых чисел), упакованные в BitSet по 8 на байт, составляют 2 ^ 32/2 ^ 3 = 2 ^ 29 = приблизительно 0,5 Гб.

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

Фактически BitSet.nextClearBit (0) сообщит вам первый неустановленный бит.

Глядя на API BitSet, кажется, что он поддерживает только 0..MAX_INT, поэтому вам может понадобиться 2 BitSet - один для положительных чисел и один для отрицательных чисел, но требования к памяти не меняются.

Если ограничения по размеру нет, самый быстрый способ - взять длину файла и сгенерировать длину файла + 1 число случайных цифр (или просто «11111 ...»). Преимущество: вам даже не нужно читать файл, и вы можете минимизировать использование памяти почти до нуля. Недостаток: вы напечатаете миллиарды цифр.

Однако, если бы единственным фактором была минимизация использования памяти, а все остальное не важно, это было бы оптимальным решением. Это может даже принести вам награду за "худшее нарушение правил".

Если мы предположим, что диапазон чисел всегда будет 2 ^ n (четная степень 2), то исключающее ИЛИ будет работать (как показано на другом плакате). Что же касается почему, давайте докажем это:

Теория

Учитывая любой диапазон целых чисел, основанный на 0, в котором есть 2^n элементов с отсутствующим одним элементом, вы можете найти этот отсутствующий элемент, просто скомпилировав известные значения вместе, чтобы получить отсутствующее число.

Доказательство

Давайте посмотрим на 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-битных целых числа (игнорируя любую память, потребляемую дескриптором файла). И он делает один проход файла.

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

Алгоритм для произвольных диапазонов

Этот алгоритм будет работать для диапазонов от любого начального числа до любого конечного числа, пока общий диапазон равен 2 ^ n ... Это в основном перебазирует диапазон, чтобы он имел минимум 0. Но для этого требуется 2 прохода. через файл (первый получает минимум, второй вычисляет отсутствующее int).

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;

Вопрос с подвохом, если он не был неправильно процитирован. Просто прочтите файл один раз, чтобы получить максимальное целое число n, и верните n+1.

Конечно, вам понадобится план резервного копирования на случай, если n+1 вызовет целочисленное переполнение.

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

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

Должен вывести 10 ^bitcount - 1, который всегда будет больше, чем 2 ^bitcount. Технически, вам нужно побить число 2 ^bitcount - (4 * 10 ⁹ - 1), поскольку вы знаете, что есть (4 миллиарда - 1) другие целые числа в файле, и даже при идеальном сжатии они занимают не менее одного бита каждое.

• Самый простой подход - найти минимальное число в файле и вернуть на 1 меньше этого числа. При этом используется память O (1) и время O (n) для файла из n чисел. Однако это не удастся, если диапазон номеров ограничен, что может сделать min-1 не-числом.

• О простом и понятном способе использования растрового изображения уже упоминалось. Этот метод использует время и память O (n).

• Также упоминался двухпроходный метод с 2 ^ 16 счетными ведрами. Он читает 2 * n целых чисел, поэтому использует время O (n) и хранилище O (1), но не может обрабатывать наборы данных с более чем 2 ^ 16 числами. Однако его легко расширить до (например) 2 ^ 60 64-битных целых чисел, запустив 4 прохода вместо 2, и легко адаптировать к использованию крошечной памяти, используя только столько ячеек, сколько помещается в памяти, и соответственно увеличивая количество проходов в в этом случае время выполнения больше не O (n), а вместо этого O (n * log n).

• Метод XOR'ing всех чисел вместе, упомянутый до сих пор rfrankel и подробно ircmaxell, отвечает на вопрос, заданный в stackoverflow # 35185, как указал ltn100. Он использует O (1) хранилище и время выполнения O (n). Если на данный момент мы примем 32-битные целые числа, XOR имеет 7% вероятность получения отличного числа. Обоснование: учитывая ~ 4G различных чисел, объединенных XOR вместе, и прибл. 300M не в файле, количество установленных битов в каждой битовой позиции имеет равные шансы быть нечетным или четным. Таким образом, 2 ^ 32 числа имеют равную вероятность возникновения в результате XOR, из которых 93% уже находятся в файле. Обратите внимание: если не все числа в файле различны, вероятность успеха метода XOR возрастает.

Почему-то, как только я прочитал эту задачу, я подумал о диагонализации. Я предполагаю сколь угодно большие целые числа.

Прочтите первое число. Заполните его слева нулевыми битами, пока не получите 4 миллиарда битов. Если первый (старший) бит равен 0, вывести 1; иначе выведите 0. (Вам действительно не нужно вводить левую клавиатуру: вы просто выводите 1, если в числе недостаточно битов.) Сделайте то же самое со вторым числом, за исключением того, что используйте его второй бит. Продолжайте просматривать файл таким же образом. Вы будете выводить 4-миллиардное число по одному биту за раз, и это число не будет таким же, как любое в файле. Доказательство: это было то же самое, что и n-е число, тогда они согласились бы на n-й бит, но они не согласны по построению.

Вы можете использовать битовые флаги, чтобы отметить, присутствует ли целое число или нет.

После обхода всего файла просканируйте каждый бит, чтобы определить, существует ли номер или нет.

Предполагая, что каждое целое число является 32-битным, они будут удобно помещаться в 1 ГБ ОЗУ, если выполняется битовая маркировка.

Удалите из файла пробелы и нечисловые символы и добавьте 1. Теперь ваш файл содержит единственный номер, не указанный в исходном файле.

Из Reddit, автор: Carbonetc.

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

Пусть все возможные целые числа будут диапазоном от int_min до int_max, а bool isNotInFile(integer) функцией, которая возвращает истину, если файл не содержит определенного целого числа, и ложь иначе (путем сравнения этого определенного целого числа с каждым целым числом в файле)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

Для ограничения памяти 10 МБ:

1. Преобразуйте число в его двоичное представление.
2. Создайте двоичное дерево, где left = 0 и right = 1.
3. Вставьте каждое число в дерево, используя его двоичное представление.
4. Если число уже было вставлено, листы уже будут созданы.

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

Число 4 миллиарда = 2 ^ 32, то есть 10 МБ может быть недостаточно.

ИЗМЕНИТЬ

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

ИЗМЕНИТЬ II

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

Отвечу на версию на 1 ГБ:

В вопросе недостаточно информации, поэтому сначала выскажу некоторые предположения:

Целое число составляет 32 бита в диапазоне от -2 147 483 648 до 2 147 483 647.

Псевдокод:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

Пока мы даем творческие ответы, вот еще один.

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

Удаление битов

Один из способов - удалить биты, однако на самом деле это может не дать результата (скорее всего, нет). Псевдокод:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

Количество битов

Следите за счетчиком битов; и используйте биты с наименьшим количеством для генерации значения. Опять же, это не гарантирует создания правильного значения.

Логика диапазона

Следите за списком упорядоченных диапазонов (отсортированных по началу). Диапазон определяется структурой:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

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

2 ^{128 * 10 18} + 1 (что составляет (2 ⁸) ^{16 * 10 18 < / sup> +1) - разве это не универсальный ответ на сегодняшний день? Это представляет собой число, которое не может быть сохранено в файле размером 16 EB, который является максимальным размером файла в любой текущей файловой системе.}

Я думаю, что это решенная проблема (см. Выше), но есть интересный случай, о котором следует помнить, потому что его могут спросить:

Если имеется ровно 4294967295 (2 ^ 32-1) 32-битных целых чисел без повторов и, следовательно, отсутствует только одно, есть простое решение.

Начните промежуточный итог с нуля и для каждого целого числа в файле добавьте это целое число с 32-битным переполнением (фактически runningTotal = (runningTotal + nextInteger)% 4294967296). После завершения добавьте 4294967296/2 к промежуточной сумме, опять же с 32-битным переполнением. Вычтите это из 4294967296, и результат будет отсутствующим целым числом.

Проблема «только одно отсутствующее целое число» решается только одним запуском и только 64 битами ОЗУ, выделенными для данных (32 для промежуточного итога, 32 для чтения в следующем целом числе).

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

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

Как сказал Райан в основном, отсортируйте файл, а затем перейдите к целым числам, и когда значение пропущено, оно у вас есть :)

РЕДАКТИРОВАТЬ при отрицательном голосовании: OP упомянул, что файл можно отсортировать, поэтому это допустимый метод.

Если вы не предполагаете 32-битное ограничение, просто верните случайно сгенерированное 64-битное число (или 128-битное, если вы пессимист). Вероятность столкновения 1 in 2^64/(4*10^9) = 4611686018.4 (примерно 1 из 4 миллиардов). Вы будете правы в большинстве случаев!

(Шутка ... вроде.)

Для входного файла с четырьмя миллиардами целых чисел предоставьте алгоритм для генерации целого числа, которого нет в файле. Предположим, у вас есть 1 ГиБ памяти. Следуйте инструкциям, которые вы бы сделали, если бы у вас было всего 10 МБ памяти.

Размер файла 4 * 109 * 4 байта = 16 ГиБ

В случае 32-битного целого числа без знака

0 <= Number < 2^32
0 <= Number < 4,294,967,296

Предлагаемое мной решение: C ++ без проверки ошибок

#include <vector>
#include <fstream>
#include <iostream>
using namespace std;

int main ()
{
    const long SIZE = 1L << 32;

    std::vector<bool> checker(SIZE, false);

    std::ifstream infile("file.txt");  // TODO: error checking

    unsigned int num = 0;

    while (infile >> num)
    {
        checker[num] = true ;
    }

    infile.close();

    // print missing numbers

    for (long i = 0; i < SIZE; i++)
    {
        if (!checker[i])
            cout << i << endl ;
    }

    return 0;
}

Сложность

• Пробел ~ 2 ³² бит = 2 ²⁹ байтов = 2 ¹⁹ КБ = 2 ⁹ МБ = 1/2 ГБ
• Время ~ Один проход
• Полнота ~ Да

Возможно, я полностью упускаю суть этого вопроса, но вы хотите найти целое число, отсутствующее в отсортированном файле целых чисел?

Эээ ... правда? Давайте подумаем, как бы выглядел такой файл:

1 2 3 4 5 6 ... первое отсутствующее число ... и т. Д.

Решение этой проблемы кажется тривиальным.

Вам не нужно их сортировать, просто несколько раз разбивайте их на части.

Первый шаг похож на первый проход быстрой сортировки. Выберите одно из целых чисел x и с его помощью выполните проход по массиву, чтобы поместить все значения меньше x слева от него и значения больше x справа. Найдите, на какой стороне x больше всего доступных слотов (целых чисел нет в списке). Это легко вычислить, сравнив значение x с его положением. Затем повторите разделение в подсписке с этой стороны от x. Затем повторите разделение в подподсписок с наибольшим количеством доступных целых чисел и т. Д. Общее количество сравнений, чтобы перейти к пустому диапазону, должно быть около 4 миллиардов, плюс-минус.

Вы можете ускорить поиск отсутствующих целых чисел после чтения существующих, сохранив диапазоны непосещенных целых чисел в некоторой древовидной структуре.

Вы должны начать с сохранения [0..4294967295] и каждый раз, когда вы читаете целое число, вы объединяете диапазон, в который оно попадает, удаляя диапазон, когда он становится пустым. В конце у вас есть точный набор целых чисел, отсутствующих в диапазонах. Итак, если вы видите 5 как первое целое число, у вас будут [0..4] и [6..4294967295].

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

Одним из способов хранения такого дерева было бы B-дерево с началом диапазона в качестве ключа и концом диапазона в качестве значения. В худшем случае использование будет, когда вы получите все нечетные или четные целые числа, что будет означать хранение 2 ^ 31 значений или десятков ГБ для дерева ... Ой. В лучшем случае это отсортированный файл, в котором для всего дерева нужно использовать только несколько целых чисел.

Так что не совсем правильный ответ, но я подумал, что упомяну этот способ. Полагаю, я бы провалил собеседование ;-)

Возможно, я читаю это слишком внимательно, но в вопросе говорится: «генерировать целое число, которого нет в файле». Я просто отсортирую список и добавлю 1 к максимальной записи. Бам, целое число, которого нет в файле.

Я придумал следующий алгоритм.

Моя идея: пройти через весь файл целых чисел один раз и для каждой битовой позиции посчитать его нули и единицы. Количество нулей и единиц должно быть 2 ^ (numOfBits) / 2, поэтому, если количество меньше ожидаемого, мы можем использовать его из нашего полученного числа.

Например, предположим, что целое число 32-битное, тогда нам потребуется

int[] ones = new int[32];
int[] zeroes = new int[32];

Для каждого числа мы должны перебрать 32 бита и увеличить значение 0 или 1:

for(int i = 0; i < 32; i++){
   ones[i] += (val>>i&0x1); 
   zeroes[i] += (val>>i&0x1)==1?0:1;
}

Наконец, после обработки файла:

int res = 0;
for(int i = 0; i < 32; i++){
   if(ones[i] < (long)1<<31)res|=1<<i;
}
return res;

ПРИМЕЧАНИЕ: в некоторых языках (например, Java) 1 ‹---------------- 31 - отрицательное число, поэтому (длинное) 1 ‹› 31 - правильный способ сделать это.

Старый вопрос, но меня интересуют «нефункциональные» требования. На мой взгляд, здесь должна быть подсказка - если этот вопрос был задан где-то еще, а не в книге, в которой затем обсуждаются все возможности с плюсами и минусами. Достаточно часто кажется, что это вопросы на собеседовании, оставляя меня озадаченным, поскольку нельзя дать однозначный ответ, не зная мягких требований, то есть «поиск недостающих чисел должен быть очень быстрым, потому что он используется x раз в секунду. ".

Думаю, на такой вопрос можно было бы дать разумный ответ.

• Я бы слил-отсортил все числа в новый файл, используя 4 байта на int. Конечно, поначалу это будет происходить медленно. Но это можно сделать с небольшим объемом памяти (необязательно хранить все в ОЗУ).
• Используйте двоичный поиск, чтобы проверить, существует ли номер в предварительно отсортированном файле. Поскольку мы остаемся 4 байтами на значение, это не проблема

недостатки:

• Размер файла
• Медленная первая сортировка - но требуется только один раз

преимущества:

• очень быстро искать

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

Конечно, имея ограниченный опыт (только что начал изучать java в Uni), вы можете запустить хотя бы один набор (бочонок) int, а если число не найдено, избавьтесь от бочки. Это освободит место и запустит проверку каждой единицы данных. Если то, что вы ищете, будет найдено, добавьте его в счетную переменную. Это займет много времени, но если вы создадите несколько переменных для каждого раздела и проведете счетчик проверок для каждой переменной и убедитесь, что они выходят / удаляются одновременно, хранилище переменных не должно увеличиваться? И ускорит процесс проверки. Просто мысль.