Один элемент, который отличается двумя массивами. Как найти это эффективно?

22

Я готовлюсь к собеседованию по кодированию и не могу найти самый эффективный способ решения этой проблемы.

Допустим, у нас есть два массива, состоящих из несортированных чисел. Массив 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. Повторяйте, пока не закончите. Это должно быть около времени выполнения, верно?O(nlogn)

Константино Спаракис
источник
@Jandvorak Спасибо, ребята, за ответы. Я опоздал и случайно заснул после публикации этого. Массив не отсортирован, и все элементы появляются со случайными индексами в обоих массивах.
Константино Спаракис
@KonstantinoSparakis: это уточнение делает недействительными ответы, которые предполагают, что оба массива содержат элементы в одинаковых позициях.
Марио Сервера
Перекрестная публикация осуждается на softwareengineering.stackexchange.com/users/256931/…
paparazzo
@Paparazzi Просто искал решение, которое я прочитал в метапрограммировании, было, где найти решение, но в то время я не знал о форуме CS. Я уведомил моды, чтобы очистить его.
Константино Спаракис
@ Папарацци, есть ли мета-пост, подтверждающий это? Лично я не вижу способа хорошо реализовать эту политику.
Джечлин

Ответы:

30

Я вижу четыре основных способа решения этой проблемы с различным временем выполнения:

  • решение: это будет решение, которое вы предлагаете. Обратите внимание, что, поскольку массивы не отсортированы, удаление занимает линейное время. Вы выполняете n удалений; следовательно, этот алгоритм занимает квадратичное время.O(n2)n

  • решение: предварительно отсортируйте массивы; затем выполните линейный поиск, чтобы определить отдельный элемент. В этом решении во время выполнения преобладает операция сортировки, следовательно, O ( nO(nlogn) верхняя граница.O(nlogn)

Когда вы определяете решение проблемы, вы всегда должны спросить себя: могу ли я сделать лучше? В этом случае вы можете, грамотно используя структуры данных. Обратите внимание, что все, что вам нужно сделать, это перебрать один массив и выполнить повторный поиск в другом массиве. Какая структура данных позволяет выполнять поиск в (ожидаемое) постоянное время? Вы правильно догадались: хеш-таблица .

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

Если вам нужны гарантии с верхней границей, а массивы строго состоят из целых чисел, возможно, лучшим решением будет то, которое предложил Тоби Алафин (хотя это решение не даст вам индекс элемента, который отличается во втором массиве) :

  • решение (гарантировано): суммировать элементы первого массива. Затем суммируйте элементы второго массива. Наконец, выполните вычитание. Обратите внимание, что это решение может быть обобщено для любого типа данных, значения которого могут быть представлены в виде битовых строк фиксированной длины, благодаряпобитовому оператору XOR. Это подробно объясняется вответеИльмари Каронена. O(n)

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

Марио Сервера
источник
4
суммирование не является линейным, если числа становятся достаточно большими.
Сардж Борщ
9
Одна приятная вещь в алгоритме суммирования состоит в том, что он работает с любой абелевой группой, а не только с целыми числами (в частности uint64,; cc @sarge).
Джон Дворжак
6
@Abdul дело в том, что если ваши целые числа очень большие, вы больше не можете притворяться, что они берут для добавления. Я считаю, что сложность возрастает до O ( n ln n ), если учесть это. Использование XOR вместо обычного сложения решает эту проблему, хотя, тем не менее, учитывает произвольно большое количество входных данных. O(n)O(nlnn)
Джон Дворжак
2
@JanDvorak Нет, это не так. Вы предполагаете, что операция, определенная для абелевой группы, занимает постоянное время. Это не может быть просто предположено.
UTF-8
2
@ UTF-8 Я этого не предполагаю. Но это происходит в конечных группах (uint64), и сложение по цифрам на месте (сложение в ) является линейным по размеру операнда вне места. Таким образом, вычисление суммы в таких группах является линейным временем в общем размере операндов. Znd
Джон Дворжак
16

Решение разности сумм, предложенное Тоби и Марио, может быть фактически обобщено для любого другого типа данных, для которого мы можем определить двоичную операцию (с постоянным временем) ⊕, которая:Θ(n)

  • всего , таким образом, что при любых значениях и б , б определена и те же типа (или , по меньшей мере , некоторые соответствующего надтип него, для которого оператор по - прежнему определяется);abab
  • ассоциативный , такой, что ;a(bc)=(ab)c
  • коммутативный , такой, что ; иab=ba
  • сократимая , таким образом, что существует обратный оператор , который удовлетворяет условию ( б ) б = . Технически, эта обратная операция даже не обязательно должна иметь постоянное время, если «вычитание» двух сумм из n элементов каждый не займет больше O ( n ) времени.(ab)b=anO(n)

(Если тип может принимать только конечное число различных значений, этих свойств достаточно, чтобы превратить его в абелеву группу ; даже если нет, он будет, по крайней мере, коммутативной полугруппой сокращения .)

a=(a1,a2,,an)

(a)=a1a2an.
b=(b1,b2,,bn,bn+1)ax(b)=(a)x
x=(b)(a).

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

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

1001232длиной в байты мы могли бы закодировать длину каждой строки как 32-разрядное целое и добавить ее к строке. Или мы могли бы даже кодировать произвольные длины строк, используя некоторый префиксный код , и добавлять их к строкам. Существуют и другие возможные кодировки.

Θ(n)

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

Илмари Каронен
источник
Вау, очень интересно взять это. Спасибо @IlmariKaronen
Константино Спаракис
14

Я бы опубликовал это как комментарий к ответу Тоби, но у меня пока нет репутации.

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

Просто вычислите xor-сумму (т. Е. X [0] ^ x [1] ^ x [2] ... x [n]) каждого списка, а затем xor этих двух значений. Это даст вам ценность постороннего предмета (но не индекса).

Это все еще O (n) и позволяет избежать проблем с переполнением.

reffu
источник
3
Я бы также использовал XOR, потому что он выглядит немного лучше, но, честно говоря, переполнение на самом деле не проблема, если язык, в котором вы реализуете это, поддерживает переполнение путем переноса.
Мартин Эндер
14

Элемент = Сумма (Массив2) - Сумма (Массив1)

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

Если количество добавленных элементов больше одного, это не сработает.

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

РЕДАКТИРОВАТЬ
После некоторых размышлений, я думаю, что мой ответ - ваше решение.

nn11=n12=n+11=n

2n121=1

2n1+1=2n

Θ(n)

РЕДАКТИРОВАТЬ:
Из-за некоторых проблем с типами данных сумма XOR, как предложено reffu, будет более подходящим.

Тоби Алафин
источник
Обратите внимание, что этот метод может не дать точного ответа, если ваши значения являются числами с плавающей запятой, поскольку суммирование чисел может привести к ошибкам округления. Тем не менее, он будет работать для целочисленных значений, при условии, что либо a) ваш целочисленный тип имеет четко определенное поведение при переполнении при переполнении, либо b) вы храните суммы в переменных достаточно широкого типа, чтобы они не могли переполниться.
Ильмари Каронен
Класс Ruby "BigNum", вероятно, может справиться с этим.
Тоби Алафин
Это абсолютно не работает, если ваш массив содержит, например, строки, или что-то, что не может быть добавлено по смыслу.
gnasher729
Да, я понял. А как насчет использования XOR? Будет ли это работать для поплавков?
Тоби Алафин
Да, а также указатели и вообще все, что состоит из битов с фиксированным числом. Многие языки не поддерживают это, но это не принципиальная проблема. Модульное сложение / вычитание будет работать в тех же случаях.
Гарольд
1

Предполагая, что массив 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, не полагаясь на утверждение, что существует еще один дополнительный вещь.

gnasher729
источник
Этот ответ был точным, но вопрос был отредактирован с новым требованием, которое опровергает ваше предположение.
Марио Сервера
Ваш новый ответ кажется правильным. Какова сложность Времени.
Тоби Алафин
Ну, во-первых, сколько времени нужно для написания кода. Это тривиально. NSCagedSet использует хеширование, поэтому временная сложность обычно "линейна".
gnasher729
-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];});

Крейг Хардкасл
источник
Коды без объяснения не считается хорошим ответом здесь. Кроме того, почему вы используете !!! ?
Зло
-1

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" Надеюсь, это решит вашу проблему. Также предложенные выше решения также хорошо

Sillymistake
источник