Недавно я увидел этот код Javascript в StackOverflow для объединения двух массивов и удаления дубликатов:
Array.prototype.unique = function() {
var a = this.concat();
for(var i=0; i<a.length; ++i) {
for(var j=i+1; j<a.length; ++j) {
if(a[i] === a[j])
a.splice(j--, 1);
}
}
return a;
};
var array1 = ["Vijendra","Singh"];
var array2 = ["Singh", "Shakya"];
var array3 = array1.concat(array2).unique();
Хотя этот код работает, он ужасно неэффективен ( O(n^2)
). Ваша задача - создать алгоритм с меньшей сложностью.
Критерием выигрыша является решение с наименьшей сложностью , но связи будут разорваны по кратчайшей длине символов.
Требования :
Упакуйте весь ваш код в функцию, которая отвечает следующим требованиям «правильности»:
- Вход: два массива
- Выход: один массив
- Объединяет элементы обоих массивов вместе. Любой элемент в любом входном массиве должен быть в выходном массиве.
- Выводимый массив не должен иметь дубликатов.
- Заказ не имеет значения (в отличие от оригинала)
- Любой язык имеет значение
- Не используйте функции массивов стандартной библиотеки для обнаружения уникальности или объединения наборов / массивов (хотя в стандартной библиотеке все в порядке). Позвольте мне сделать различие, что конкатенация массива - это хорошо, но функции, которые уже выполняют все вышеперечисленное, - нет.
[1, 2, 2, 3]
и[2, 3, 4]
возврат[1, 2, 2, 3, 4]
или[1, 2, 3, 4]
?Ответы:
Perl
27 персонажей
Простой Perl Hack
Я уверен, что кто-то мог бы это сделать одним ударом ... и, таким образом (спасибо Dom Hastings)
источник
sub x{$_{$_}++for@_;keys%_}
(в случае, если дело доходит до ничьей!) И использовать в качестве:z((1,2,3,4),(2,3,4,5,6))
JavaScript O (N)
13112411692 (86?)Гольф версия:
Читаемая человеком версия для гольфа:
Я мог бы использовать
concat
так и сделать это в 86 символов:Но я не уверен, что это все еще O (N) на основе этого JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping, так как версия concat немного быстрее с меньшими массивами, но медленнее с большие массивы (Chrome 31 OSX).
На практике сделайте это (в гольфе полно плохих практик):
Я не очень хорош в вычислительной сложности, но я верю, что это так
O(N)
. Хотелось бы, чтобы кто-то мог уточнить.Редактировать: вот версия, которая принимает любое количество массивов и объединяет их.
источник
O(N)
.O(A*B)
(не используется,N
потому что это сбивает с толку). Было бы так, что если бы каждый входной массив (каждыйA
) имел такое же количество элементов (B
), как и на самом делеO(SUM(B) FOR ALL A)
, которое можно переписать, какO(N)
при определенииN
количества элементов всех входов массива.Python 2.7, 38 символов
Должно быть O (N) при условии хорошей хеш-функции.
set
Реализация 8-ми символов в Wasi лучше, если вы не думаете, что это нарушает правила.источник
PHP,
69/4268/41 символовВ том числе объявление функции составляет 68 символов:
Не включая объявление функции 41 символа:
источник
Один путь в Руби
Чтобы придерживаться правил, изложенных выше, я бы использовал стратегию, аналогичную решению JavaScript, и использовал бы хэш в качестве посредника.
По сути, это шаги, которые я прохожу в строке выше.
merged_arr
которая будет содержать результатObject#tap
для заполнения хеша (на который ссылается какhash
вtap
блоке) и возврата его для последующего объединения методовarr1
иarr2
в один необработанный массивel
в каскадном массиве, поместить значениеel
в ,hash[el]
если значения вhash[el]
настоящее время не существует. Запоминание здесь (hash[el] ||= el
) - это то, что обеспечивает уникальность элементов.Это должно бежать
O(n)
вовремя. Пожалуйста, дайте мне знать, если я сделал какие-либо неточные утверждения или смогу ли я улучшить ответ выше для эффективности или удобочитаемости.Возможные улучшения
Использование мемоизации, вероятно, не нужно, учитывая, что ключи хеша будут уникальными, а значения не имеют значения, поэтому этого достаточно:
Я действительно люблю
Object#tap
, но мы можем достичь того же результата, используяEnumerable#reduce
:Вы могли бы даже использовать
Enumberable#map
:Как бы я это делал на практике
Сказав все это, если бы меня попросили объединить два массива
arr1
иarr2
таким образом, что результатmerged_arr
имеет уникальные элементы и могут использовать любой метод Ruby , в моем распоряжении, я бы просто использовать оператор набора накидной , который предназначен для решения этой точной задачи:Быстрый взгляд на источник
Array#|
, тем не менее, подтверждает, что использование хэша в качестве посредника кажется приемлемым решением для выполнения уникального слияния двух массивов.источник
Функция, которая будет принимать n массивов, может быть следующей:
Гольф, я думаю, это должно работать (117 символов)
Обновление Если вы хотите сохранить исходный тип, вы можете
или игра в гольф 149:
Это все еще может вызвать некоторые сомнения, если вы хотите различить,
123
и'123'
это не будет работать ..источник
O(N)
)?m([1,2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7])
становится["1", "2", "3", "4", "5", "6", "7"]
питон, 46
Или просто используя операцию set
питона, 8
источник
Perl
23 байта, если мы только посчитаем кодовый блок внутри подпрограммы. Может быть 21, если разрешена перезапись глобальных значений (это приведет к удалению
my
из кода). Он возвращает элементы в случайном порядке, потому что порядок не имеет значения. Что касается сложности, то в среднем это O (N) (зависит от количества коллизий хэшей, но они довольно редки - в худшем случае это может быть O (N 2 ) (но этого не должно быть, потому что Perl может обнаруживать патологические хэши и изменяет начальное значение хэш-функции при обнаружении такого поведения)).Вывод (также показывает случайность):
источник
Фортран:
282252233213Гольф версия:
Который не только выглядит бесконечно лучше, но и на самом деле будет компилировать (слишком длинная строка в форме для гольфа) с удобочитаемой формой:
Это должно быть ,
O(n)
как я копируюa
в ,c
а затем проверить каждыйb
против всехc
. Последний шаг - удалить мусор, которыйc
будет содержаться, поскольку он не инициализирован.источник
Mathematica 10 символов
Пример:
Mathematica2 43 символа
источник
Tally[Join[a, b]][[;; , 1]]
что это также будет обманывать ;-) Кстати, вы могли бы сохранить символы с помощью однобуквенных переменных.Javascript 86
Гольф версия:
Читаемая версия:
источник
m([1,0,0,0,0],[0,1,0])
возвращается[1]
.h[v]=v
наh[v]=1
.JavaScript 60
Я использую генератор ES6.
Следующее можно проверить с помощью Google Traceur REPL .
источник
Если вы ищете эффективную реализацию на основе JavaScript, основанную на базовых объектах, лежащих в основе фреймворка, я бы просто использовал Set. Обычно в реализации объект Set по своей сути обрабатывает уникальные объекты во время вставки с помощью своего рода индексации двоичного поиска. Я знаю, что в Java это
log(n)
поиск, использующий бинарный поиск, основанный на том факте, что ни один набор не может содержать один объект более одного раза.Хотя я понятия не имею, верно ли это и для Javascript, для
n*log(n)
реализации может быть достаточно чего-то простого, например, следующего фрагмента :JavaScript , 61 байт
Попробуйте онлайн!
Если приведенный выше фрагмент использует
a = [1,2,3]
иb = [1,2,3,4,5,6]
затемs=[1,2,3,4,5,6]
.Если вы знаете , сложность
Set.add(Object)
функции в JavaScript , дайте мне знать, сложность этого ,n + n * f(O)
гдеf(O)
есть сложностьs.add(O)
.источник
APL (Dyalog Unicode) , O (N), 28 байт
Анонимная функция молчаливого инфикса.
Попробуйте онлайн!
,
объединить аргументы; НА)(
…)
Примените к нему следующую анонимную молчаливую функцию; O (1)⍳⍨
индексы селфи (индексы первого появления каждого элемента во всем массиве); НА)=
сравнить элемент за элементом с; НА):⍳∘≢
индексы длины массива; НА)(/⍨)
используйте это для фильтрации; НА):⊢
неизмененный аргумент; O (1)O (N + 1 + N + N + N + N + 1) = O (N)
источник
JavaScript, 131 символ
источник
PHP около 28 символов [исключая переменные массива и переменную результата].
$ array1 = array (1, 2, 3); $ array2 = array (3, 4, 5);
$ result = array_merge ($ array1, $ array2);
источник