Небольшое серое во время воспоминания о времени интервью со сцены ......
тема: в неупорядоченном массиве имеется 99 неповторяющихся положительных целых чисел в диапазоне от 1 до 100, за исключением одного пропущенного целого числа. Как узнать это пропущенное целое число?
Решение первое:
Создайте HashMap с ключами от 1 до 100 и значениями 0. Затем пройдитесь по всему массиву, каждый раз, когда читается целое число, найдите соответствующий ключ в HashMap и добавьте единицу к его значению.
Из-за отсутствия целого числа в массиве в итоге должно остаться 99 ключей, значение которых равно 1, и оставшийся один ключ, значение которого равно 0. Пройдитесь по измененному HashMap, чтобы найти ключ, значение которого равно 0.
Если предположить, что длина массива равна N, то временная сложность этого решения равна O (1), а пространственная сложность — O (N).
Решение второе:
Сначала отсортируйте элементы массива, а затем просмотрите массив, чтобы проверить, имеют ли какие-либо два соседних элемента последовательные значения. Если не последовательно, то отсутствующее целое число в середине — это то, что вы ищете; если все подряд, отсутствующее целое число равно 1 или 100.
Предполагая, что длина массива равна N, если для сортировки используется алгоритм сортировки с временной сложностью O(N*LogN), то временная сложность решения равна O(N*LogN), а пространственная сложность равна O( 1).
Решение третье:
Очень простой и эффективный метод, сначала вычислите комбинацию 1+2+3....+100, затем вычтите элементы в массиве по очереди, и в итоге полученная разница будет единственным недостающим целым числом.
Если предположить, что длина массива равна N, то временная сложность этого решения равна O(N), а пространственная сложность — O(1).
Расширение заголовка: неупорядоченный массив имеет ряд положительных целых чисел в диапазоне от 1 до 100, из которых 99 пострадали четное целое число раз, было только одно целое нечетное число раз (например, 1,1,2,2, 3,3,4 , 5,5), как найти это нечетное целое число?
решение:
Перебирает весь массив и по очереди выполняет операцию XOR. Поскольку одно и то же равно 0, а разница равна 1 в битовой операции, все целые числа, встречающиеся четное количество раз, будут компенсировать друг друга, чтобы стать 0, и останется только единственное целое число, которое появляется нечетное количество раз.
Если предположить, что длина массива равна N, то временная сложность этого решения равна O(N), а пространственная сложность — O(1).
Второе расширение темы: в неупорядоченном массиве есть несколько положительных целых чисел в диапазоне от 1 до 100, из которых 98 целых чисел встречаются четное количество раз, толькодваЦелое число появляется нечетное количество раз (например, 1, 1, 2, 2, 3, 4, 5, 5), как найти целое число, которое встречается нечетное количество раз?
решение:
Перебирает весь массив и по очереди выполняет операцию XOR. Поскольку два целых числа встречаются в массиве нечетное количество раз, окончательный результат XOR эквивалентен результату XOR этих двух целых чисел. В этом результате хотя бы один двоичный бит равен 1 (если оба равны 0, два числа равны, что не соответствует заголовку).
Например, если окончательный результат XOR равен 5, преобразованный в двоичный файл, он будет 00000101. На этом этапе мы можем выбрать для анализа любой двоичный бит, равный 1, например, последний бит. Назовите два целых числа, которые встречаются в нечетных числах, как A и B. Если последняя цифра равна 1, это означает, что последняя цифра A и B, преобразованная в двоичную систему, различна, и последняя цифра одного из целых чисел должна быть 1, и последняя цифра другого целого числа равна 0. .
Согласно этому выводу, мы можем разделить исходный массив на две части в соответствии с последней цифрой двоичного числа, одна часть равна 1, а последняя часть равна 0. Поскольку последние позиции А и В различны, А находится в одной части, а В — в одной части, и никогда не будет ситуации, когда А и В находятся в одной части, а другая часть — нет.
Таким образом, это просто, и наша проблема возвращается к ситуации предыдущего вопроса.Согласно исходному решению XOR, мы можем найти уникальное нечетное целое число из каждой части.
Если предположить, что длина массива равна N, то временная сложность этого решения равна O(N). Разделение массива на две части не требует дополнительного места для хранения, а операция XOR может выполняться при группировке по двоичным битам, поэтому объемная сложность по-прежнему составляет O(1).
Десять минут спустя......
Вышеуказанная ситуация собеседования Сяо Хуэй ...
----КОНЕЦ----
Друзья, которым понравилась эта статья, нажмите и удерживайте изображение, чтобы следить за номером подписки.программист маленький серый, смотрите больше захватывающего контента