Я готовлюсь к собеседованию по кодированию и не могу найти самый эффективный способ решения этой проблемы.
Допустим, у нас есть два массива, состоящих из несортированных чисел. Массив 2 содержит число, которого нет в массиве 1. Оба массива имеют случайно расположенные числа, не обязательно в одном и том же порядке или с одинаковыми индексами. Например:
Массив 1 [78,11, 143, 84, 77, 1, 26, 35 .... n]
Массив 2 [11,84, 35, 25, 77, 78, 26, 143 ... 21 ... n + 1]
Какой самый быстрый алгоритм поиска числа, которое отличается? Каково его время работы? В этом примере число, которое мы будем искать, равно 21.
Моя идея состояла в том, чтобы запустить массив 1 и удалить это значение из массива 2. Повторяйте, пока не закончите. Это должно быть около времени выполнения, верно?
источник
Ответы:
Я вижу четыре основных способа решения этой проблемы с различным временем выполнения:
решение: это будет решение, которое вы предлагаете. Обратите внимание, что, поскольку массивы не отсортированы, удаление занимает линейное время. Вы выполняете n удалений; следовательно, этот алгоритм занимает квадратичное время.O ( n2) N
решение: предварительно отсортируйте массивы; затем выполните линейный поиск, чтобы определить отдельный элемент. В этом решении во время выполнения преобладает операция сортировки, следовательно, O ( nO ( nл о гн ) верхняя граница.O ( nл о гн )
Когда вы определяете решение проблемы, вы всегда должны спросить себя: могу ли я сделать лучше? В этом случае вы можете, грамотно используя структуры данных. Обратите внимание, что все, что вам нужно сделать, это перебрать один массив и выполнить повторный поиск в другом массиве. Какая структура данных позволяет выполнять поиск в (ожидаемое) постоянное время? Вы правильно догадались: хеш-таблица .
Если вам нужны гарантии с верхней границей, а массивы строго состоят из целых чисел, возможно, лучшим решением будет то, которое предложил Тоби Алафин (хотя это решение не даст вам индекс элемента, который отличается во втором массиве) :
Наконец, другая возможность (при том же предположении целочисленных массивов) будет использовать алгоритм сортировки с линейным временем, такой как сортировка по счету. Это сократит время выполнения решения на основе сортировки от до O ( n ) .O ( nл о гн ) O ( n )
источник
uint64
,; cc @sarge).Решение разности сумм, предложенное Тоби и Марио, может быть фактически обобщено для любого другого типа данных, для которого мы можем определить двоичную операцию (с постоянным временем) ⊕, которая:Θ(n) ⊕
(Если тип может принимать только конечное число различных значений, этих свойств достаточно, чтобы превратить его в абелеву группу ; даже если нет, он будет, по крайней мере, коммутативной полугруппой сокращения .)
В более общем смысле, мы можем даже применить побитовый метод XOR к строкам переменной длины, дополняя их до той же длины, что и при необходимости, при условии, что у нас есть некоторый способ обратимо удалить заполнение в конце.
В некоторых случаях это тривиально. Например, строки байтов с нулевым символом в конце в стиле C неявно кодируют свою собственную длину, поэтому применение этого метода для них тривиально: когда XOR обрабатывает две строки, дополняет более короткую строку нулевыми байтами, чтобы соответствовать их длине, и обрезает любые дополнительные завершающие нули из конечный результат. Обратите внимание, что промежуточные строки XOR-суммы могут содержать нулевые байты, поэтому вам нужно явно хранить их длину (но вам понадобится только один или два из них максимум).
Единственная потенциально сложная часть заключается в том, что для отмены работы нам нужно выбрать уникальное каноническое представление цепочки битов для каждого значения, что может быть трудным (даже потенциально неразрешимым с точки зрения вычислений), если могут быть заданы входные значения в двух массивах. в разных эквивалентных представлениях. Это не особая слабость этого метода, однако; любой другой метод решения этой проблемы также может быть потерпел неудачу, если входные данные могут содержать значения, эквивалентность которых неразрешима.
источник
Я бы опубликовал это как комментарий к ответу Тоби, но у меня пока нет репутации.
В качестве альтернативы для вычисления суммы каждого списка (особенно, если они являются большими списками или содержат очень большие числа, которые могут переполнять ваш тип данных при суммировании), вы можете использовать вместо этого xor.
Просто вычислите xor-сумму (т. Е. X [0] ^ x [1] ^ x [2] ... x [n]) каждого списка, а затем xor этих двух значений. Это даст вам ценность постороннего предмета (но не индекса).
Это все еще O (n) и позволяет избежать проблем с переполнением.
источник
Элемент = Сумма (Массив2) - Сумма (Массив1)
Я искренне сомневаюсь, что это самый оптимальный алгоритм. Но это еще один способ решения проблемы и самый простой способ ее решения. Надеюсь, это поможет.
Если количество добавленных элементов больше одного, это не сработает.
Мой ответ имеет одинаковую сложность во время выполнения для лучшего, худшего и среднего случая,
РЕДАКТИРОВАТЬ
После некоторых размышлений, я думаю, что мой ответ - ваше решение.
РЕДАКТИРОВАТЬ:
Из-за некоторых проблем с типами данных сумма XOR, как предложено reffu, будет более подходящим.
источник
Предполагая, что массив 2 был создан путем взятия массива 1 и вставки элемента в произвольную позицию, или массив 1 был создан путем взятия массива 2 и удаления случайного элемента.
Если все элементы массива гарантированно различаются, время равно O (ln n). Вы сравниваете элементы в местоположении n / 2. Если они равны, дополнительный элемент имеет значение от n / 2 + 1 до конца массива, в противном случае - от 0 до n / 2. И так далее.
Если не гарантируется, что элементы массива будут различаться: у вас может быть n раз число 1 в массиве 1 и число 2, вставленное в любое место массива 2. В этом случае вы не можете знать, где находится число 2, не глядя на все элементы массива. Следовательно, O (n).
PS. Поскольку требования изменились, проверьте свою библиотеку на предмет того, что доступно. В macOS / iOS вы создаете NSCountingSet, добавляете все числа из массива 2, удаляете все числа из массива 1, и остается только все, что находится в массиве 2, но не в массиве 1, не полагаясь на утверждение, что существует еще один дополнительный вещь.
источник
var самый короткий, самый длинный;
Преобразование кратчайшего в карту для быстрой ссылки и цикл по самому длинному до тех пор, пока текущего значения нет на карте.
Примерно так в javascript:
if (arr1.length> arr2.length) {shorttest = arr2; самый длинный = arr1; } else {shorttest = arr1; самый длинный = обр2; }
var map = shorttest.reduce (function (obj, value) {obj [value] = true; вернуть obj;}, {});
var diff = longest.find (function (value) {return !!! map [value];});
источник
O (N) решение во временной сложности O (1) в терминах пространственной сложности
Постановка задачи: Предполагая, что array2 содержит все элементы array1 плюс еще один элемент, отсутствующий в array1.
Решение: мы используем xor, чтобы найти элемент, которого нет в array1, поэтому выполните следующие шаги: 1. Начните с array1 и выполните xor для всех элементов и сохраните их в переменной. 2. Возьмите array2 и выполните xor всех элементов с переменной, в которой хранится xor для array1. 3. После выполнения операции наша переменная будет содержать элемент, который присутствует только в array2. Приведенный выше алгоритм работает из-за следующего свойства xor "a xor a = 0" "a xor 0 = a" Надеюсь, это решит вашу проблему. Также предложенные выше решения также хорошо
источник