Array Gabung tanpa Duplikat

15

Saya baru-baru ini melihat kode Javascript ini di StackOverflow untuk menggabungkan dua array , dan menghapus duplikat:

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(); 

Sementara kode ini berfungsi, itu sangat tidak efisien (O(n^2) ). Tantangan Anda adalah membuat algoritma dengan kompleksitas yang lebih sedikit.

Kriteria yang menang adalah solusi dengan kompleksitas paling sedikit , tetapi hubungan akan terputus dengan karakter terpendek.

Persyaratan :

Kemas semua kode Anda bersama-sama dalam suatu fungsi yang memenuhi persyaratan berikut untuk "kebenaran:"

  • Input: Dua array
  • Output: Satu array
  • Menggabungkan elemen dari kedua array secara bersamaan- Setiap elemen dalam array input harus dalam array yang di-output.
  • Array yang dihasilkan tidak boleh memiliki duplikat.
  • Pesanan tidak masalah (tidak seperti yang asli)
  • Bahasa apa pun penting
  • Jangan gunakan fungsi array perpustakaan standar untuk mendeteksi keunikan atau menggabungkan set / array (meskipun hal-hal lain dari perpustakaan standar baik-baik saja). Biarkan saya membuat perbedaan bahwa rangkaian array baik-baik saja, tetapi fungsi yang sudah melakukan semua hal di atas tidak.
hkk
sumber
Bagaimana seharusnya kita membuat atau menambahkan ke array tanpa menggunakan fungsi array?
Emil Vikström
@ EmilVikström Lihat hasil edit saya. Maksud saya, Anda tidak dapat menggunakan fungsi keunikan array. Maaf karena tidak jelas.
hkk
Jika salah satu array memiliki duplikat di dalamnya, apakah kami juga menghapusnya? Misalnya, haruskah penggabungan [1, 2, 2, 3]dan [2, 3, 4]pengembalian [1, 2, 2, 3, 4]atau [1, 2, 3, 4]?
OI
1
@ OI Ya, itu akan membuatnya terlalu mudah.
hkk
1
Bolehkah saya bertanya: Susunan apa ? Bisakah kita mengasumsikan bilangan bulat atau string, atau apakah kita juga harus mengizinkan hal-hal yang lebih kompleks seperti objek bertingkat?
jawns317

Jawaban:

8

Perl

27 Karakter

Perl Hack Sederhana

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

Saya yakin seseorang dapat melakukan one-liner ini .. dan karenanya (Terima kasih Dom Hastings)

sub x{$_{$_}++for@_;keys%_}
Zach Leighton
sumber
1
"Jangan gunakan fungsi array perpustakaan standar untuk mendeteksi keunikan (meskipun hal-hal lain membentuk perpustakaan standar tidak apa-apa)"
John Dvorak
1
Bagaimana saya melanggar aturan itu? Saya tidak menggunakan fungsi unik?
Zach Leighton
Bagaimana cara kerjanya? Maaf, saya tidak dapat membaca perl. Jika membaca kunci peta hash - apakah itu dianggap OK dengan aturan itu? Saya tidak akan memilih sampai yakin itu benar.
John Dvorak
1
Ini menggabungkan array, loop atas keduanya dan menambah hash yang menambah nilai siapa kunci adalah nilai saat ini dalam loop array. Kemudian dibutuhkan kunci hash itu, saya telah menggunakan ini dalam beberapa pekerjaan saya .. Jadi [1,1,2,3,4,4] menjadi {1 => 2, 2 => 1, 3 => 1 , 4 => 2}
Zach Leighton
@ ZachLeighton Anda dapat mempersingkat kode menjadi 27 karakter sub x{$_{$_}++for@_;keys%_}(jika itu turun ke dasi!) Dan gunakan sebagai:z((1,2,3,4),(2,3,4,5,6))
Dom Hastings
10

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

Versi golf:

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}

Versi golf yang dapat dibaca manusia:

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
}

Saya bisa menggunakan concatsuka dan melakukannya dalam 86 karakter:

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

Tapi saya tidak yakin apakah masih O (N) berdasarkan JsPerf ini: http://jsperf.com/unique-array-merging-concat-vs-looping karena versi concat sedikit lebih cepat dengan array yang lebih kecil tetapi lebih lambat dengan array yang lebih besar (Chrome 31 OSX).

Dalam latihan lakukan ini (golf penuh dengan praktik buruk):

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]));

Saya tidak hebat dalam kompleksitas komputasi tetapi saya percaya ini O(N). Akan senang jika seseorang bisa mengklarifikasi.

Sunting: Ini adalah versi yang mengambil sejumlah array dan menggabungkannya.

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]));
George Reith
sumber
Ini hampir persis apa yang akan saya posting dalam beberapa detik :-( Ya, ini adalah waktu linier diamortisasi jika tabel hash diimplementasikan dengan waktu konstan diamortisasi untuk penyisipan dan pencarian (yang umum dalam banyak bahasa, tidak tahu secara khusus tentang JS)
Emil Vikström
@ EmilVikström Terima kasih untuk itu saya yakin JavaScript tidak memiliki bukti. Permintaan maaf karena memiliki jari yang cepat, memperlambat diri Anda dengan komentar: P
George Reith
Ini adalah pendekatan yang bagus. Namun, dapatkah Anda juga memberikan solusi gaya "kode-golf" selain versi yang diformat dengan baik? Melihat bahwa banyak orang menganggap ini sebagai pendekatan yang tepat, mungkin akan ada ikatan O(N).
hkk
@ cloudcoder2000 Oke, saya ingin mencetak versi lengkap karena versi kode-golf cenderung kurang efisien dalam praktiknya.
George Reith
1
@ cloudcoder2000 Mereka tidak sepenuhnya independen sehingga kasus terburuknya tidak O(A*B)(Tidak menggunakan Nkarena membingungkan). Ini akan menjadi bahwa jika setiap array input (setiap A) memiliki jumlah elemen yang sama ( B) seperti yang sebenarnya O(SUM(B) FOR ALL A), yang dapat ditulis ulang seperti O(N)ketika mendefinisikan Nsebagai jumlah elemen dari semua input array.
meiamsome
4

Python 2.7, 38 karakter

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

Seharusnya O (N) dengan asumsi fungsi hash yang baik.

setImplementasi 8 karakter Wasi lebih baik, jika Anda tidak berpikir itu melanggar aturan.

Keith Randall
sumber
Bagus! Pemahaman dalam Python bisa sangat elegan dan kuat.
OI
3

PHP, 69/42 68/41 chars

Termasuk deklarasi fungsi adalah 68 karakter:

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

Tidak termasuk deklarasi fungsi adalah 41 karakter:

array_keys(array_flip($a)+array_flip($b))
kacang zam
sumber
3

Satu jalan di Ruby

Untuk tetap mengikuti aturan yang diuraikan di atas, saya akan menggunakan strategi yang sama dengan solusi JavaScript dan menggunakan hash sebagai perantara.

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

Pada dasarnya, ini adalah langkah-langkah yang saya lalui pada baris di atas.

  1. Tentukan variabel merged_arr yang akan berisi hasil
  2. Inisialisasi hash kosong dan tanpa nama sebagai perantara untuk memasukkan elemen unik ke dalam
  3. Gunakan Object#tapuntuk mengisi hash (dirujuk seperti hashdalam tapblok) dan mengembalikannya untuk rangkaian metode berikutnya
  4. Menggabungkan arr1dan arr2menjadi satu, array yang belum diproses
  5. Untuk setiap elemen eldalam array bersambung, menempatkan nilai eldalam hash[el]jika tidak ada nilai hash[el]saat ini ada. Memoisasi di sini ( hash[el] ||= el) adalah yang memastikan keunikan elemen.
  6. Ambil kunci (atau nilai, karena sama) untuk hash yang sekarang diisi

Ini harus dijalankan O(n) tepat waktu. Tolong beri tahu saya jika saya telah membuat pernyataan yang tidak akurat atau jika saya dapat meningkatkan jawaban di atas untuk efisiensi atau keterbacaan.

Kemungkinan peningkatan

Menggunakan memoisasi mungkin tidak perlu mengingat bahwa kunci hash akan menjadi unik dan nilainya tidak relevan, jadi ini sudah cukup:

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

Saya sangat suka Object#tap, tetapi kami dapat mencapai hasil yang sama menggunakan Enumerable#reduce:

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

Anda bahkan dapat menggunakan Enumberable#map:

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

Bagaimana saya akan melakukannya dalam latihan

Setelah mengatakan semua itu, jika saya diminta untuk menggabungkan dua array arr1dan arr2sedemikian rupa sehingga hasilnya merged_arrmemiliki elemen unik dan dapat menggunakan metode Ruby apa pun yang saya inginkan, saya hanya akan menggunakan set union operator yang dimaksudkan untuk menyelesaikan masalah yang tepat ini:

merged_arr = arr1 | arr2

Mengintip cepat pada sumbernya Array#|, bagaimanapun, tampaknya mengkonfirmasi bahwa menggunakan hash sebagai perantara tampaknya menjadi solusi yang dapat diterima untuk melakukan penggabungan unik antara 2 array.

OI
sumber
"Jangan menggunakan fungsi array perpustakaan standar untuk mendeteksi keunikan (meskipun hal-hal lain membentuk perpustakaan standar tidak apa-apa)"
John Dvorak
Bagaimana saya melanggar aturan itu dalam contoh kedua? Memoisasi sedang dilakukan di hash. Apakah itu tidak diizinkan?
OI
2
Array.prototype.unique = function()
{
  var o = {},i = this.length
  while(i--)o[this[i]]=true
  return Object.keys(o)
}

Fungsi yang akan mengambil n array bisa sebagai berikut:

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);
}

Golf, saya pikir ini seharusnya berhasil (117 karakter)

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)}

Perbarui Jika Anda ingin mempertahankan jenis aslinya, Anda bisa

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
}

atau bermain golf 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}

Ini masih dapat menimbulkan beberapa keraguan, jika Anda ingin membedakan 123dan '123', maka ini tidak akan berhasil ..

Konijn
sumber
Terima kasih atas jawabannya. Itu sangat pendek, namun ini hanya setengah dari masalah. Anda juga perlu memasukkan dalam solusi bagian penggabungan yang sebenarnya (bahkan jika itu sama seperti dalam contoh asli) dan menempatkan semuanya bersama dalam satu fungsi. Selain itu, dapatkah Anda memberikan versi "golf" sebagai tambahan untuk ini (sebagaimana adanya O(N))?
hkk
Ini melemparkan semua anggota ke string. misalnya m([1,2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7])menjadi["1", "2", "3", "4", "5", "6", "7"]
George Reith
2

python, 46

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

Atau, menggunakan operasi yang ditetapkan secara sederhana

python, 8

set(a+b)
Wasi
sumber
1
Maaf tidak jelas, menggunakan operasi yang ditetapkan juga curang.
hkk
Kode 1 Anda akan memiliki duplikat jika ada duplikat di a atau jika ada duplikat di b dan elemen itu tidak ada dalam a.
Vedant Kandoi
2

Perl

23 byte, jika kita hanya menghitung blok kode di dalam subrutin. Bisa jadi 21, jika ditimpa nilai global diizinkan (itu akan menghapus mydari kode). Ini mengembalikan elemen dalam urutan acak, karena pesanan tidak masalah. Adapun kompleksitas, rata-rata itu O (N) (tergantung pada jumlah tabrakan hash, tetapi mereka agak jarang - dalam kasus terburuk itu bisa O (N 2 ) (tapi ini tidak boleh terjadi, karena Perl dapat mendeteksi hash patologis , dan mengubah fungsi hash seed ketika mendeteksi perilaku tersebut)).

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;

Output (juga menunjukkan keacakan):

/tmp $ perl unique.pl 
2 3 4 6 1 5
/tmp $ perl unique.pl 
5 4 6 2 1 3
Konrad Borowski
sumber
2

Fortran: 282 252 233 213

Versi golf:

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

Yang tidak hanya terlihat jauh lebih baik tetapi sebenarnya akan mengkompilasi (garis yang terlalu panjang dalam bentuk golf) dengan bentuk yang dapat dibaca manusia:

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

Ini harus O(n)seperti yang saya copy ake cdan kemudian memeriksa setiap bterhadap semua c. Langkah terakhir adalah menghilangkan sampah yang cakan mengandung karena tidak diinisialisasi.

Kyle Kanos
sumber
2

Mathematica 10 Chars

Union[a,b]

Contoh:

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

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

Mathematica2 43 Karakter

Sort@Join[a, b] //. {a___, b_, b_, c___} :> {a, b, c}
Murta
sumber
8
Saya pikir ini akan masuk dalam kategori menggunakan metode array perpustakaan standar.
hkk
Hai @ cloudcoder2000. Tidak perlu memanggil perpustakaan tertentu untuk menggunakan Union di Mathematica.
Murta
5
Menurut pendapat saya, menggunakan fungsi bawaan untuk melakukan persis apa yang diminta pertanyaan itu curang.
Konrad Borowski
ok ok .. kode kedua jangan gunakan Union.
Murta
1
Saya kira Tally[Join[a, b]][[;; , 1]]juga akan curang ;-) BTW Anda bisa menyimpan karakter dengan menggunakan variabel huruf tunggal.
Yves Klett
1

Javascript 86

Versi golf:

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

Versi yang dapat dibaca:

function merge(a, b) {
  var hash = {};
  return a.concat(b).filter(function (val) {
    return hash[val] ? 0 : hash[val] = 1;
  });
}
Bertrand
sumber
1
Ini mengabaikan nilai falsey ... m([1,0,0,0,0],[0,1,0])mengembalikan [1].
George Reith
1
Ubah h[v]=vke h[v]=1.
George Reith
@GeorgeReith terlihat bagus! Kami beralih dari 86 ke 84 :)
Bertrand
Ini masih 86, saya pikir Anda bingung karena Anda menghapus 2 karakter dari versi yang dapat dibaca bukan yang golf.
George Reith
1

JavaScript 60

Saya menggunakan generator ES6.
Berikut ini dapat diuji menggunakan Google Traceur REPL .

m=(i,j)=>{h={};return[for(x of i.concat(j))if(!h[x])h[x]=x]}
Florent
sumber
0

Jika Anda mencari implementasi berbasis JavaScript yang bergantung pada Objek di balik kerangka kerja agar efisien, saya hanya akan menggunakan Set. Biasanya dalam implementasi, objek Set secara inheren menangani objek unik selama penyisipan dengan semacam indeks pencarian biner. Saya tahu di Jawa ini adalah log(n)pencarian, menggunakan pencarian biner berdasarkan fakta bahwa tidak ada set yang dapat berisi satu objek lebih dari sekali.


Meskipun saya tidak tahu apakah ini juga berlaku untuk Javascript, sesuatu yang sederhana seperti cuplikan berikut mungkin cukup untuk n*log(n) implementasi:

JavaScript , 61 byte

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

Cobalah online!


Jika penggunaan potongan di atas a = [1,2,3]dan b = [1,2,3,4,5,6]kemudians=[1,2,3,4,5,6] .

Jika Anda tahu kompleksitas Set.add(Object)fungsi dalam JavaScript beri tahu saya, kompleksitasnya adalah di n + n * f(O)mana f(O)kompleksitasnya s.add(O).

Guci Gurita Ajaib
sumber
0

APL (Dyalog Unicode) , O (N), 28 byte

Fungsi infiks diam-diam anonim.

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

Cobalah online!

, menggabungkan argumen; DI)

(...)  terapkan fungsi diam-diam anonim berikut untuk itu; O (1)

   ⍳⍨ indeks selfie (indeks kemunculan pertama setiap elemen di seluruh array); DI)

  = bandingkan elemen demi elemen dengan; DI):

   ⍳∘≢ indeks panjang array; DI)

(/⍨) gunakan itu untuk menyaring; DI):

   argumen yang tidak dimodifikasi; O (1)

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

Adm
sumber
-2

JavaScript, 131 karakter

var array1 = ["Vijendra","Singh"];   
var array2 = ["Singh", "Shakya"];     
result = Array.from(new Set([...array1, ...array2]))
deepak_pal
sumber
4
Selamat datang di PPCG! Beri tahu kami bahasa ini dan memformatnya sebagai kode agar lebih mudah dibaca. (Ini berfungsi dengan indentasi baris kode dengan empat spasi). Juga penjelasan tentang pendekatan Anda akan dihargai.
Laikoni
itu hanya kode javascript.
deepak_pal
@techdeepak Anda dapat menambahkan informasi penting tersebut ke posting Anda, memformatnya dengan benar, menambahkan penyorotan sintaksis dan menulis lebih banyak tentang kompleksitas algoritma Anda, karena ini adalah algoritma tercepat . Seperti berdiri, posting ini memiliki kualitas yang cukup rendah.
Jonathan Frech
-2

PHP sekitar 28 karakter [meninggalkan contoh variabel array dan variabel hasil].

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

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

Endri
sumber
Dari pertanyaan: Jangan gunakan fungsi array perpustakaan standar untuk mendeteksi keunikan atau menggabungkan set / array . Selain itu, ini sebenarnya tidak menghapus duplikat dari array
Jo King
Saya pikir Anda telah mengabaikan baris penting ini dari pertanyaan: " Jangan gunakan fungsi array perpustakaan standar untuk mendeteksi keunikan atau menggabungkan set / array "
Peter Taylor
Iya. Itu benar. Terima kasih teman-teman untuk menunjukkannya. Kritik diterima dengan rendah hati.
Endri
@ raja. Anda benar tentang "Jangan gunakan perpustakaan standar ...". Sisanya salah. Itu menghapus duplikat. php.net/manual/en/function.array-merge.php . Saya sarankan Anda untuk membaca dokumentasi PHP sepenuhnya. Saya 100% yakin itu berhasil. Anda hanya perlu berhati-hati, salah satu array yang Anda anggap sebagai duplikat. Bersulang.
Endri
1
Saya benar-benar menjalankan kode dalam kiriman Anda tanpa perubahan dan hasilnya memiliki duplikat. Sepertinya Anda harus membaca dokumentasi, yaitu Jika, bagaimanapun, array berisi kunci numerik, nilai kemudian tidak akan menimpa nilai asli, tetapi akan ditambahkan
Jo King