Есть тестовая задача, я немного подсел в алгоритмах, можете подсказать какой лучше подойдет для задачи?

Question

[Алексей]

Есть массив чисел от 1 до 100000000000. Массив отсортирован(1,2,3 ....99999999999,100000000000 ), но в нем одна цифра задвоилась(Например, [1,2,3,4,4,6,7 ...]). Надо написать метод который найдет отсутствующее число за минимальное время.

Comments

[sim3x]

И в чем затруднение?

[Алексей]

sim3x, какой алогоритм применить, у меня на ум приходит возможно бинарный поиск, но кажется не самый быстрый способ

[sim3x]

Алексей Семенов,
Начните с прямого перебора

[Lynn «Кофеман»]

С чего бы очевидному бинарному поиску быть медленным?

Берём число в середине. Если оно совпадает со своим порядковым номером, то задвоение во второй половине, если на единицу меньше, то в первой половине. Продолжаем делить дальше нужную половину.

Нужно только не запутаться с индексами и значениями

[Lynn «Кофеман»]

А что сложного во второй задаче? Прочитать файл? Разбить на слова? Достать из массива каждый третий элемент?

[Алексей]

да

[Алексей]

Алексей Тен, да во второй задаче, ничего сложного) я ее сделал)

[Lynn «Кофеман»]

Сергей, цикл будет нужен что бы сумму посчитать

[MaxLich]

Что значит "подсел на алгоритмах"? Расшифруйте.

[Lynn «Кофеман»]

Сергей, а сумма чисел в массиве?

[Lynn «Кофеман»]

Сергей, а в бинарном поиске O(log n)

Answer 1

[Alexej Simakov]

В "правильной" последовательности чисел сумма каждой пары чисел, если брать с головы и с хвоста, не изменяется. Чтобы добраться до того места где спутались цифры перебором понадобится N/2, и еще нужно будет выяснить какое из двух чисел неправильное например проверив его соседей

Во второй задаче нужно разбить текст на токены

str = "Hello I'm your String";
String[] splited = str.split("\\s+");

https://stackoverflow.com/questions/7899525/how-to...
а потом пройти по массиву и выдать каждое третье слово. Вопрос еще в том, что делать со знаками препинания которые как правило прилеплены к слову. По уму их надо откинуть.

Comments

[Lynn «Кофеман»]

Первая решается за log N, а не N/2

[Алексей]

по первой задаче, а не подскажиет как объявить long массив?

[Alexej Simakov]

Алексей Тен, это утверждение которое я не могу проверить, обьясните ваш алгоритм.

[Alexej Simakov]

Алексей Семенов, а, всё, прочитал выше, согласен.

[Alexej Simakov]

Алексей Семенов, было бы варварством лишать Вас возможности узнать это самостоятельно. Любой базовый туториал по Java наведет вас на нужный ответ.

[Алексей]

Alexej Simakov, просто намек?) стоит использовать BigInteger?

[Alexej Simakov]

Алексей Семенов, long []; BigInteger имеет еще больший диапазон чем long.

[Алексей]

Alexej Simakov, ладно тогда буду искать, просто почему-то в java не устравивает long array[] = new long[100000000l]

[Alexej Simakov]

Алексей Семенов, Ява не поддерживает массивы размером больше MAXINT. т.е размерность ожидается типа int.
Уберите l в размерности, либо добавьте каст long[(int)100000000l] автоматическое приведение типов в этом случае не работает из-за возможной потери точности.
Если нужен массив очень большой придется воспользоватся структурами данных типа ArrayList

[Алексей]

Alexej Simakov, спасибо)