Слияние массивов без дубликатов

15

Недавно я увидел этот код 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)). Ваша задача - создать алгоритм с меньшей сложностью.

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

Требования :

Упакуйте весь ваш код в функцию, которая отвечает следующим требованиям «правильности»:

  • Вход: два массива
  • Выход: один массив
  • Объединяет элементы обоих массивов вместе. Любой элемент в любом входном массиве должен быть в выходном массиве.
  • Выводимый массив не должен иметь дубликатов.
  • Заказ не имеет значения (в отличие от оригинала)
  • Любой язык имеет значение
  • Не используйте функции массивов стандартной библиотеки для обнаружения уникальности или объединения наборов / массивов (хотя в стандартной библиотеке все в порядке). Позвольте мне сделать различие, что конкатенация массива - это хорошо, но функции, которые уже выполняют все вышеперечисленное, - нет.
HKK
источник
Как мы должны создавать или добавлять массив без использования функций массива?
Эмиль Викстрем
@ EmilVikström Смотрите мои изменения. Я имел в виду, что вы не можете использовать функции уникальности массива. Извините за то, что неясно.
HKK
Если в одном из массивов есть дубликаты, мы их тоже удаляем? Например, следует ли слияние [1, 2, 2, 3]и [2, 3, 4]возврат [1, 2, 2, 3, 4]или [1, 2, 3, 4]?
OI
1
@ OI Да, это слишком легко.
HKK
1
Могу я спросить: массивы чего ? Можем ли мы предполагать просто целые числа или строки, или мы также должны разрешать более сложные вещи, такие как многоуровневые объекты?
jawns317

Ответы:

8

Perl

27 персонажей

Простой Perl Hack

my @vals = ();
push @vals, @arr1, @arr2;
my %out;
map { $out{$_}++ } @vals;
my @unique = keys %out;

Я уверен, что кто-то мог бы это сделать одним ударом ... и, таким образом (спасибо Dom Hastings)

sub x{$_{$_}++for@_;keys%_}
Зак Лейтон
источник
1
«Не используйте функции массива стандартной библиотеки для определения уникальности (хотя другие вещи из стандартной библиотеки в порядке)»
Джон Дворжак
1
Как я нарушаю это правило? Я не использую уникальные функции?
Зак Лейтон
Как это работает, тогда? Извините, я не могу читать на Perl. Если он читает ключи хэш-карты - считается ли это нормальным с этим правилом? Я не буду голосовать, пока не убедлюсь, что это так.
Джон Дворжак
1
Он объединяет массивы, перебирает их и добавляет к хешу, увеличивая значение, ключ которого является текущим значением в цикле массива. Затем он берет ключи этого хэша, я использовал это в некоторых своих работах. Поэтому [1,1,2,3,4,4] становится {1 => 2, 2 => 1, 3 => 1 , 4 => 2}
Зак Лейтон
@ZachLeighton вы можете сократить код до 27 символов с помощью sub x{$_{$_}++for@_;keys%_}(в случае, если дело доходит до ничьей!) И использовать в качестве:z((1,2,3,4),(2,3,4,5,6))
Dom Hastings
10

JavaScript O (N) 131 124 116 92 (86?)

Гольф версия:

function m(i,x){h={};n=[];for(a=2;a--;i=x)i.map(function(b){h[b]=h[b]||n.push(b)});return n}

Читаемая человеком версия для гольфа:

function m(i,x) {
   h = {}
   n = []
   for (a = 2; a--; i=x)
      i.map(function(b){
        h[b] = h[b] || n.push(b)
      })
   return n
}

Я мог бы использовать concatтак и сделать это в 86 символов:

function m(i,x){h={};n=[];i.concat(x).map(function(b){h[b]=h[b]||n.push(b)});return n}

Но я не уверен, что это все еще O (N) на основе этого JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping, так как версия concat немного быстрее с меньшими массивами, но медленнее с большие массивы (Chrome 31 OSX).

На практике сделайте это (в гольфе полно плохих практик):

function merge(a1, a2) {
   var hash = {};
   var arr = [];
   for (var i = 0; i < a1.length; i++) {
      if (hash[a1[i]] !== true) {
        hash[a1[i]] = true;
        arr[arr.length] = a1[i];
      }
   }
   for (var i = 0; i < a2.length; i++) {
      if (hash[a2[i]] !== true) {
        hash[a2[i]] = true;
        arr[arr.length] = a2[i];
      }
   }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6]));

Я не очень хорош в вычислительной сложности, но я верю, что это так O(N). Хотелось бы, чтобы кто-то мог уточнить.

Редактировать: вот версия, которая принимает любое количество массивов и объединяет их.

function merge() {
   var args = arguments;
   var hash = {};
   var arr = [];
   for (var i = 0; i < args.length; i++) {
      for (var j = 0; j < args[i].length; j++) {
        if (hash[args[i][j]] !== true) {
          arr[arr.length] = args[i][j];
          hash[args[i][j]] = true;
        }
      }
    }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8]));
Джордж Райт
источник
Это почти то, что я собирался опубликовать через пару секунд :-( Да, это амортизированное линейное время, если хеш-таблицы реализованы с амортизированным постоянным временем для вставки и поиска (что часто встречается во многих языках, не знаю конкретно) о JS).
Эмиль Викстрем
@ EmilVikström Спасибо за это, я верю, что JavaScript есть, но у меня нет на это доказательств. Извиняюсь за быстрые пальцы, замедлил себя комментариями: P
Джордж Райт
Это отличный подход. Тем не менее, не могли бы вы также предложить решение в стиле "code-golf" в дополнение к вашей красиво отформатированной версии? Видя, что несколько человек думают об этом как о правильном подходе, вероятно, будет связь O(N).
HKK
@ cloudcoder2000 Хорошо, я хотел напечатать полную версию, так как версия code-golf, вероятно, будет менее эффективной на практике.
Джордж Райт
1
@ cloudcoder2000 Они не являются полностью независимыми, поэтому наихудший случай - нет O(A*B)(не используется, Nпотому что это сбивает с толку). Было бы так, что если бы каждый входной массив (каждый A) имел такое же количество элементов ( B), как и на самом деле O(SUM(B) FOR ALL A), которое можно переписать, как O(N)при определении Nколичества элементов всех входов массива.
meiamsome
4

Python 2.7, 38 символов

F=lambda x,y:{c:1 for c in x+y}.keys()

Должно быть O (N) при условии хорошей хеш-функции.

setРеализация 8-ми символов в Wasi лучше, если вы не думаете, что это нарушает правила.

Кит Рэндалл
источник
Ницца! Понимание в Python может быть таким элегантным и мощным.
OI
3

PHP, 69/42 68/41 символов

В том числе объявление функции составляет 68 символов:

function m($a,$b){return array_keys(array_flip($a)+array_flip($b));}

Не включая объявление функции 41 символа:

array_keys(array_flip($a)+array_flip($b))
zamnuts
источник
3

Один путь в Руби

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

merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] ||= el } }.keys

По сути, это шаги, которые я прохожу в строке выше.

  1. Определите переменную, merged_arrкоторая будет содержать результат
  2. Инициализируйте пустой неназванный хеш как посредника, чтобы поместить уникальные элементы в
  3. Используется Object#tapдля заполнения хеша (на который ссылается как hashв tapблоке) и возврата его для последующего объединения методов
  4. Объединить arr1и arr2в один необработанный массив
  5. Для каждого элемента elв каскадном массиве, поместить значение elв , hash[el]если значения в hash[el]настоящее время не существует. Запоминание здесь ( hash[el] ||= el) - это то, что обеспечивает уникальность элементов.
  6. Получите ключи (или значения, поскольку они одинаковы) для теперь заполненного хеша

Это должно бежать O(n)вовремя. Пожалуйста, дайте мне знать, если я сделал какие-либо неточные утверждения или смогу ли я улучшить ответ выше для эффективности или удобочитаемости.

Возможные улучшения

Использование мемоизации, вероятно, не нужно, учитывая, что ключи хеша будут уникальными, а значения не имеют значения, поэтому этого достаточно:

merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] = 1 } }.keys

Я действительно люблю Object#tap, но мы можем достичь того же результата, используя Enumerable#reduce:

merged_arr = (arr1 + arr2).reduce({}) { |arr, val| arr[val] = 1; arr }.keys

Вы могли бы даже использовать Enumberable#map:

merged_arr = Hash[(arr1 + arr2).map { |val| [val, 1] }].keys

Как бы я это делал на практике

Сказав все это, если бы меня попросили объединить два массива arr1и arr2таким образом, что результат merged_arrимеет уникальные элементы и могут использовать любой метод Ruby , в моем распоряжении, я бы просто использовать оператор набора накидной , который предназначен для решения этой точной задачи:

merged_arr = arr1 | arr2

Быстрый взгляд на источник Array#|, тем не менее, подтверждает, что использование хэша в качестве посредника кажется приемлемым решением для выполнения уникального слияния двух массивов.

О.И.
источник
«Не используйте функции массива стандартной библиотеки для определения уникальности (хотя другие вещи из стандартной библиотеки в порядке)»
Джон Дворжак
Как я нарушаю это правило во втором примере? Мемоизация выполняется по хешу. Это тоже не разрешено?
OI
2
Array.prototype.unique = function()
{
  var o = {},i = this.length
  while(i--)o[this[i]]=true
  return Object.keys(o)
}

Функция, которая будет принимать n массивов, может быть следующей:

function m()
{
  var o={},a=arguments,c=a.length,i;
  while(c--){i=a[c].length;while(i--)o[a[c][i]] = true} 
  return Object.keys(o);
}

Гольф, я думаю, это должно работать (117 символов)

function m(){var o={},a=arguments,c=a.length,i;while(c--){i=a[c].length;while(i--)o[a[c][i]]=1}return Object.keys(o)}

Обновление Если вы хотите сохранить исходный тип, вы можете

function m()
{
  var o={},a=arguments,c=a.length,f=[],g=[];
  while(c--)g.concat(a[c])
  c = g.length      
  while(c--){if(!o[g[c]]){o[g[c]]=1;f.push(g[c])}}
  return f
}

или игра в гольф 149:

function m(){var o={},a=arguments,c=a.length,f=[],g=[];while(c--)g.concat(a[c]);c= g.length;while(c--){if(!o[g[c]]){o[g[c]]=1;f.push(g[c])}}return f}

Это все еще может вызвать некоторые сомнения, если вы хотите различить, 123и '123'это не будет работать ..

Konijn
источник
Спасибо за ответ. Он впечатляюще короткий, но это только половина проблемы. Вам также необходимо включить в решение фактическую часть слияния (даже если она такая же, как в исходном примере) и объединить все это в одну функцию. Кроме того, не могли бы вы предоставить «версию для гольфа» в дополнение к этому (как она есть O(N))?
hkk
Это приводит всех участников к строкам. например m([1,2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7])становится["1", "2", "3", "4", "5", "6", "7"]
Джордж Райт
2

питон, 46

def A(a,b):print[i for i in b if i not in a]+a

Или просто используя операцию set

питона, 8

set(a+b)
Был ли я
источник
1
Извините, это не было ясно, использование операций над множествами также обманывает.
HKK
Ваш первый код будет иметь дубликаты, если в a есть дубликаты или если в b есть дубликаты, а этот элемент отсутствует в a.
Ведант Кандой
2

Perl

23 байта, если мы только посчитаем кодовый блок внутри подпрограммы. Может быть 21, если разрешена перезапись глобальных значений (это приведет к удалению myиз кода). Он возвращает элементы в случайном порядке, потому что порядок не имеет значения. Что касается сложности, то в среднем это O (N) (зависит от количества коллизий хэшей, но они довольно редки - в худшем случае это может быть O (N 2 ) (но этого не должно быть, потому что Perl может обнаруживать патологические хэши и изменяет начальное значение хэш-функции при обнаружении такого поведения)).

use 5.010;
sub unique{
    my%a=map{$_,1}@_;keys%a
}
my @a1 = (1, 2, 3, 4);
my @a2 = (3, 4, 5, 6);
say join " ", unique @a1, @a2;

Вывод (также показывает случайность):

/tmp $ perl unique.pl 
2 3 4 6 1 5
/tmp $ perl unique.pl 
5 4 6 2 1 3
Конрад Боровски
источник
2

Фортран: 282 252 233 213

Гольф версия:

function f(a,b,m,n) result(d);integer::m,n,a(m),b(n),c(m+n);integer,allocatable::d(:);j=m+1;c(1:m)=a(1:m);do i=1,n;if(.not.any(b(i)==c(1:m)))then;c(j)=b(i);j=j+1;endif;enddo;allocate(d(j-1));d=c(1:j-1);endfunction

Который не только выглядит бесконечно лучше, но и на самом деле будет компилировать (слишком длинная строка в форме для гольфа) с удобочитаемой формой:

function f(a,b,m,n) result(d)
  integer::m,n,a(m),b(n),c(m+n)
  integer,allocatable::d(:)
  j=m+1;c(1:m)=a(1:m)
  do i=1,n
     if(.not.any(b(i)==c(1:m)))then
        c(j)=b(i);j=j+1
     endif
  enddo
  allocate(d(j-1))
  d=c(1:j-1)
end function

Это должно быть , O(n)как я копирую aв , cа затем проверить каждый bпротив всех c. Последний шаг - удалить мусор, который cбудет содержаться, поскольку он не инициализирован.

Кайл Канос
источник
2

Mathematica 10 символов

Union[a,b]

Пример:

a={1,2,3,4,5};
b={1,2,3,4,5,6};
Union[a,b]

{1, 2, 3, 4, 5, 6}

Mathematica2 43 символа

Sort@Join[a, b] //. {a___, b_, b_, c___} :> {a, b, c}
Мурта
источник
8
Я думаю, что это относится к категории использования стандартных методов библиотечного массива.
HKK
Привет @ cloudcoder2000. Не нужно вызывать какую-то конкретную библиотеку, чтобы использовать Union в Mathematica.
Мурта
5
По моему мнению, использование встроенной функции для того, чтобы сделать именно то, о чем просит вопрос, - обман.
Конрад Боровски
хорошо хорошо .. второй код не использовать Союз.
Мурта
1
Я думаю, Tally[Join[a, b]][[;; , 1]]что это также будет обманывать ;-) Кстати, вы могли бы сохранить символы с помощью однобуквенных переменных.
Ив Клетт
1

Javascript 86

Гольф версия:

function m(a,b){var h={};return a.concat(b).filter(function(v){return h[v]?0:h[v]=1})}

Читаемая версия:

function merge(a, b) {
  var hash = {};
  return a.concat(b).filter(function (val) {
    return hash[val] ? 0 : hash[val] = 1;
  });
}
Bertrand
источник
1
Это игнорирует ложные значения ... m([1,0,0,0,0],[0,1,0])возвращается [1].
Джордж Райт
1
Изменить h[v]=vна h[v]=1.
Джордж Райт
Хорошо заметили @GeorgeReith! Мы пошли с 86 на 84 :)
Бертран
Это все еще 86, я думаю, вы запутались, потому что вы удалили 2 символа из читаемой версии, а не в гольф.
Джордж Райт
1

JavaScript 60

Я использую генератор ES6.
Следующее можно проверить с помощью Google Traceur REPL .

m=(i,j)=>{h={};return[for(x of i.concat(j))if(!h[x])h[x]=x]}
Флоран
источник
0

Если вы ищете эффективную реализацию на основе JavaScript, основанную на базовых объектах, лежащих в основе фреймворка, я бы просто использовал Set. Обычно в реализации объект Set по своей сути обрабатывает уникальные объекты во время вставки с помощью своего рода индексации двоичного поиска. Я знаю, что в Java это log(n)поиск, использующий бинарный поиск, основанный на том факте, что ни один набор не может содержать один объект более одного раза.


Хотя я понятия не имею, верно ли это и для Javascript, для n*log(n)реализации может быть достаточно чего-то простого, например, следующего фрагмента :

JavaScript , 61 байт

var s = new Set(a);      // Complexity O(a.length)
b.forEach(function(e) {  // Complexity O(b.length) * O(s.add())
  s.add(e);
}); 

Попробуйте онлайн!


Если приведенный выше фрагмент использует 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).

Урна волшебного осьминога
источник
0

APL (Dyalog Unicode) , O (N), 28 байт

Анонимная функция молчаливого инфикса.

(⊢(/⍨)⍳∘≢=⍳⍨),

Попробуйте онлайн!

, объединить аргументы; НА)

() Примените к нему следующую анонимную молчаливую функцию; O (1)

   ⍳⍨ индексы селфи (индексы первого появления каждого элемента во всем массиве); НА)

  = сравнить элемент за элементом с; НА):

   ⍳∘≢ индексы длины массива; НА)

(/⍨) используйте это для фильтрации; НА):

   неизмененный аргумент; O (1)

O (N + 1 + N + N + N + N + 1) = O (N)

Адам
источник
-2

JavaScript, 131 символ

var array1 = ["Vijendra","Singh"];   
var array2 = ["Singh", "Shakya"];     
result = Array.from(new Set([...array1, ...array2]))
deepak_pal
источник
4
Добро пожаловать в PPCG! Пожалуйста, сообщите нам, какой это язык, и отформатируйте его как код для лучшей читаемости. (Это работает путем отступа строк кода с четырьмя пробелами). Также будет приветствоваться объяснение вашего подхода.
Лайкони
это просто код JavaScript.
deepak_pal
@techdeepak Вы можете добавить такую ​​важную информацию в свой пост, правильно отформатировать ее, добавить подсветку синтаксиса и написать немного больше о сложности вашего алгоритма, так как это самый быстрый алгоритм . Этот пост довольно низкого качества.
Джонатан Фрех
-2

PHP около 28 символов [исключая переменные массива и переменную результата].

$ array1 = array (1, 2, 3); $ array2 = array (3, 4, 5);

$ result = array_merge ($ array1, $ array2);

Endri
источник
Из вопроса: не используйте функции массива стандартной библиотеки для обнаружения уникальности или объединения наборов / массивов . Кроме того, это фактически не удаляет дубликаты из массива
Джо Кинг,
Я думаю, что вы пропустили эту важную строку из вопроса: « Не используйте функции массивов стандартной библиотеки для обнаружения уникальности или объединения наборов / массивов »
Питер Тейлор,
Да. Правильно. Спасибо, ребята, что указали на это. Критика смиренно принята.
Endri
@ Джо Кинг. Вы абсолютно правы насчет "Не используйте стандартные библиотеки ...". Остальное не так. Это действительно удаляет дубликаты. php.net/manual/en/function.array-merge.php . Я рекомендую вам полностью прочитать документацию PHP. Я на 100% уверен, что это делает работу. Вам просто нужно быть осторожным, какой из массивов вы считаете дубликатами. Приветствия.
Endri
1
Я буквально запустил код в вашем представлении без изменений, и на выходе есть дубликаты. Похоже, вам следует прочитать документацию, а именно: если, однако, массивы содержат цифровые клавиши, более позднее значение не будет перезаписывать исходное значение, а будет добавлено
Джо Кинг,