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.
[1, 2, 2, 3]
dan[2, 3, 4]
pengembalian[1, 2, 2, 3, 4]
atau[1, 2, 3, 4]
?Jawaban:
Perl
27 Karakter
Perl Hack Sederhana
Saya yakin seseorang dapat melakukan one-liner ini .. dan karenanya (Terima kasih Dom Hastings)
sumber
sub x{$_{$_}++for@_;keys%_}
(jika itu turun ke dasi!) Dan gunakan sebagai:z((1,2,3,4),(2,3,4,5,6))
JavaScript O (N)
13112411692 (86?)Versi golf:
Versi golf yang dapat dibaca manusia:
Saya bisa menggunakan
concat
suka dan melakukannya dalam 86 karakter: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):
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.
sumber
O(N)
.O(A*B)
(Tidak menggunakanN
karena membingungkan). Ini akan menjadi bahwa jika setiap array input (setiapA
) memiliki jumlah elemen yang sama (B
) seperti yang sebenarnyaO(SUM(B) FOR ALL A)
, yang dapat ditulis ulang sepertiO(N)
ketika mendefinisikanN
sebagai jumlah elemen dari semua input array.Python 2.7, 38 karakter
Seharusnya O (N) dengan asumsi fungsi hash yang baik.
set
Implementasi 8 karakter Wasi lebih baik, jika Anda tidak berpikir itu melanggar aturan.sumber
PHP,
69/4268/41 charsTermasuk deklarasi fungsi adalah 68 karakter:
Tidak termasuk deklarasi fungsi adalah 41 karakter:
sumber
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.
Pada dasarnya, ini adalah langkah-langkah yang saya lalui pada baris di atas.
merged_arr
yang akan berisi hasilObject#tap
untuk mengisi hash (dirujuk sepertihash
dalamtap
blok) dan mengembalikannya untuk rangkaian metode berikutnyaarr1
danarr2
menjadi satu, array yang belum diprosesel
dalam array bersambung, menempatkan nilaiel
dalamhash[el]
jika tidak ada nilaihash[el]
saat ini ada. Memoisasi di sini (hash[el] ||= el
) adalah yang memastikan keunikan elemen.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:
Saya sangat suka
Object#tap
, tetapi kami dapat mencapai hasil yang sama menggunakanEnumerable#reduce
:Anda bahkan dapat menggunakan
Enumberable#map
:Bagaimana saya akan melakukannya dalam latihan
Setelah mengatakan semua itu, jika saya diminta untuk menggabungkan dua array
arr1
danarr2
sedemikian rupa sehingga hasilnyamerged_arr
memiliki 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: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.sumber
Fungsi yang akan mengambil n array bisa sebagai berikut:
Golf, saya pikir ini seharusnya berhasil (117 karakter)
Perbarui Jika Anda ingin mempertahankan jenis aslinya, Anda bisa
atau bermain golf 149:
Ini masih dapat menimbulkan beberapa keraguan, jika Anda ingin membedakan
123
dan'123'
, maka ini tidak akan berhasil ..sumber
O(N)
)?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"]
python, 46
Atau, menggunakan operasi yang ditetapkan secara sederhana
python, 8
sumber
Perl
23 byte, jika kita hanya menghitung blok kode di dalam subrutin. Bisa jadi 21, jika ditimpa nilai global diizinkan (itu akan menghapus
my
dari 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)).Output (juga menunjukkan keacakan):
sumber
Fortran:
282252233213Versi golf:
Yang tidak hanya terlihat jauh lebih baik tetapi sebenarnya akan mengkompilasi (garis yang terlalu panjang dalam bentuk golf) dengan bentuk yang dapat dibaca manusia:
Ini harus
O(n)
seperti yang saya copya
kec
dan kemudian memeriksa setiapb
terhadap semuac
. Langkah terakhir adalah menghilangkan sampah yangc
akan mengandung karena tidak diinisialisasi.sumber
Mathematica 10 Chars
Contoh:
Mathematica2 43 Karakter
sumber
Tally[Join[a, b]][[;; , 1]]
juga akan curang ;-) BTW Anda bisa menyimpan karakter dengan menggunakan variabel huruf tunggal.Javascript 86
Versi golf:
Versi yang dapat dibaca:
sumber
m([1,0,0,0,0],[0,1,0])
mengembalikan[1]
.h[v]=v
keh[v]=1
.JavaScript 60
Saya menggunakan generator ES6.
Berikut ini dapat diuji menggunakan Google Traceur REPL .
sumber
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
Cobalah online!
Jika penggunaan potongan di atas
a = [1,2,3]
danb = [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 din + n * f(O)
manaf(O)
kompleksitasnyas.add(O)
.sumber
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)
sumber
JavaScript, 131 karakter
sumber
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);
sumber