Satu elemen yang berbeda dalam dua array. Bagaimana cara menemukannya secara efisien?

Saya sedang mempersiapkan wawancara pengkodean dan saya benar-benar tidak tahu cara paling efisien untuk menyelesaikan masalah ini.

Katakanlah kita memiliki dua array yang terdiri dari angka yang tidak disortir. Array 2 berisi angka yang tidak dimiliki Array 1. Kedua array memiliki angka lokasi yang acak, tidak harus dalam urutan yang sama atau pada indeks yang sama. Sebagai contoh:

Array 1 [78,11, 143, 84, 77, 1, 26, 35 .... n]

Array 2 [11,84, 35, 25, 77, 78, 26, 143 ... 21 ... n + 1]

Apa algoritma tercepat untuk menemukan nomor yang berbeda? Apa itu waktu berjalan? Dalam contoh ini, nomor yang akan kita cari adalah 21.

Ide saya adalah menjalankan melalui Array 1 dan menghapus nilai itu dari array 2. Iterate sampai Anda selesai. Ini harus sekitar waktu berjalan, kan?$O(n \log n)$

Saya melihat empat cara utama untuk mengatasi masalah ini, dengan waktu berlari yang berbeda:

• $O(n^2)$Solusi : ini akan menjadi solusi yang Anda usulkan. Perhatikan bahwa, karena array tidak disortir, penghapusan membutuhkan waktu linier. Anda melakukan penghapusan; oleh karena itu, algoritma ini membutuhkan waktu kuadratik.$n$

• solusi: urutkan array sebelumnya; kemudian, lakukan pencarian linier untuk mengidentifikasi elemen yang berbeda. Dalam solusi ini, waktu berjalan didominasi oleh operasi penyortiran, karenanya O ( $O(n \: log \: n)$ batas atas.$O(n \: log \: n)$

Ketika Anda mengidentifikasi solusi untuk suatu masalah, Anda harus selalu bertanya pada diri sendiri: dapatkah saya berbuat lebih baik? Dalam hal ini, Anda bisa, memanfaatkan struktur data dengan cerdas. Perhatikan bahwa yang perlu Anda lakukan adalah mengulangi satu larik dan melakukan pencarian berulang-ulang di larik lainnya. Struktur data apa yang memungkinkan Anda melakukan pencarian dalam waktu konstan (diharapkan)? Anda menebak dengan benar: tabel hash .

• solusi (diharapkan): iterate array pertama dan simpan elemen dalam tabel hash; kemudian, lakukan pemindaian linier di array kedua, cari setiap elemen dalam tabel hash. Kembalikan elemen yang tidak ditemukan di tabel hash. Solusi linear-waktu ini berfungsi untuk semua jenis elemen yang Anda bisa lewati ke fungsi hash (misalnya, itu akan bekerja sama untuk array string).$O(n)$

Jika Anda ingin jaminan batas atas dan array terdiri dari integer, solusi terbaik adalah, mungkin, yang disarankan oleh Tobi Alafin (meskipun solusi ini tidak akan memberi Anda indeks elemen yang berbeda dalam array kedua) :

• solusi (dijamin): jumlahkan elemen dari array pertama. Kemudian, jumlahkan elemen-elemen dari array kedua. Akhirnya, lakukan substraksi. Perhatikan bahwa solusi ini sebenarnya dapat digeneralisasi ke semua tipe data yang nilainya dapat direpresentasikan sebagai string bit panjang tetap, berkatoperator XOR bitwise. Ini sepenuhnya dijelaskan dalamjawabanIlmari Karonen. $O(n)$

Akhirnya, kemungkinan lain (dengan asumsi array integer yang sama) adalah menggunakan algortihm pengurutan linear-time seperti penghitungan sortir. Ini akan mengurangi waktu berjalan solusi berbasis penyortiran dari hingga O ( n ) .$O(n \: log \: n)$$O(n)$

The perbedaan-jumlah yang diusulkan olehTobidanMariosebenarnya dapat digeneralisasi ke tipe data lain yang kita dapat mendefinisikan operasi biner (waktu konstan) ⊕ yaitu:$\Theta(n)$$\oplus$

• total , sehingga untuk nilai apa pun dan $a$$b$ , didefinisikan dan dari jenis yang sama (atau setidaknya beberapa supertype yang tepat itu, yang operator ⊕ masih ditentukan);$a \oplus b$$\oplus$
• asosiatif , sehingga ;$a \oplus (b \oplus c) = (a \oplus b) \oplus c$
• komutatif , seperti itu ; dan$a \oplus b = b \oplus a$
• pembatalan , sedemikian sehingga terdapat operator terbalik yang memenuhi ( a ⊕ b ) ⊖ b = a . Secara teknis, operasi terbalik ini bahkan tidak harus waktu yang konstan, selama "mengurangi" dua jumlah$\ominus$$(a \oplus b) \ominus b = a$ elemen yang masing-masing tidak memerlukan waktu lebih dari O ( n ) .$n$${\rm O}(n)$

(Jika tipe hanya dapat mengambil sejumlah nilai berbeda, properti ini cukup untuk membuatnya menjadi grup Abelian ; bahkan jika tidak, itu setidaknya akan menjadi semigroup pembatalan komutatif .)

Menggunakan operasi semacam itu , kita dapat mendefinisikan "jumlah" dari array a = ( a 1 , a 2 , $\oplus$$a = (a_1, a_2, \dots, a_n)$

$\oplus$$\ominus$$\oplus$$\ominus$

Secara lebih umum, kita bahkan dapat menerapkan metode XOR bitwise ke string dengan panjang variabel, dengan menambahkan mereka ke panjang yang sama seperti yang diperlukan, selama kita memiliki beberapa cara untuk menghapus pembalikan padding di akhir.

Dalam beberapa kasus, ini sepele. Sebagai contoh, C-style null terminasi byte string secara implisit mengkodekan panjangnya sendiri, jadi menerapkan metode ini untuk mereka adalah sepele: ketika XORing dua string, pad yang lebih pendek dengan null byte untuk membuat panjangnya cocok, dan pangkas setiap tambahan trailing nulls dari hasil akhir. Perhatikan bahwa string XOR-jumlah menengah dapat berisi byte nol, jadi Anda harus menyimpan panjangnya secara eksplisit (tetapi paling banyak hanya membutuhkan satu atau dua dari mereka).

$1$$0$$0$$1$$2^{32}$byte panjang, kita bisa menyandikan panjang setiap string sebagai integer 32-bit dan menambahkannya ke string. Atau kita bahkan bisa menyandikan panjang string acak menggunakan beberapa kode awalan , dan menambahkannya ke string. Penyandian lain yang mungkin ada juga.

$\Theta(n)$

Satu-satunya bagian yang berpotensi rumit adalah bahwa, untuk pembatalan agar berfungsi, kita perlu memilih representasi bitstring kanonik unik untuk setiap nilai, yang mungkin sulit (memang, bahkan berpotensi secara komputasi tidak dapat dipastikan) jika nilai input dalam dua array dapat diberikan dalam representasi setara yang berbeda. Namun ini bukan kelemahan spesifik dari metode ini; metode lain untuk memecahkan masalah ini juga dapat dibuat gagal jika input diizinkan mengandung nilai yang ekivalennya tidak dapat diputuskan.

Saya akan memposting ini sebagai komentar atas jawaban Tobi, tetapi saya belum memiliki reputasi.

Sebagai alternatif untuk menghitung jumlah setiap daftar (terutama jika mereka adalah daftar besar atau berisi angka yang sangat besar yang mungkin meluap tipe data Anda saat dijumlahkan) Anda dapat menggunakan xor sebagai gantinya.

Hitung saja xor-sum (yaitu x [0] ^ x [1] ^ x [2] ... x [n]) dari setiap daftar dan kemudian xor kedua nilai tersebut. Ini akan memberi Anda nilai item asing (tapi bukan indeks).

Ini masih O (n) dan menghindari masalah dengan luapan.

Elemen = Jumlah (Array2) - Jumlah (Array1)

Saya dengan tulus ragu ini adalah algoritma yang paling optimal. Tapi ini cara lain untuk menyelesaikan masalah, dan merupakan cara paling sederhana untuk menyelesaikannya. Semoga ini bisa membantu.

Jika jumlah elemen yang ditambahkan lebih dari satu, ini tidak akan berhasil.

Jawaban saya memiliki kompleksitas run time yang sama untuk kasus terbaik, terburuk, dan rata-rata,

EDIT
Setelah beberapa pemikiran, saya pikir jawaban saya adalah solusi Anda.

$n$$n-1$$1 = n-1$$2 = n+1 -1=n$

$2n-1$$2 -$$1 = 1$

$2n - 1 + 1 = 2n$

EDIT:
Karena beberapa masalah dengan tipe data, jumlah XOR seperti yang disarankan oleh reffu akan lebih tepat.

Dengan asumsi bahwa array 2 dibuat dengan mengambil array 1 dan memasukkan elemen pada posisi acak, atau array 1 dibuat dengan mengambil array 2 dan menghapus elemen acak.

Jika semua elemen array dijamin berbeda, waktunya adalah O (ln n). Anda membandingkan elemen di lokasi n / 2. Jika mereka sama, elemen tambahan adalah dari n / 2 + 1 hingga akhir array, jika tidak dari 0 hingga n / 2. Dan seterusnya.

Jika elemen array tidak dijamin berbeda: Anda bisa memiliki n kali angka 1 dalam array 1, dan angka 2 dimasukkan di mana saja dalam array 2. Dalam hal ini Anda tidak bisa tahu di mana angka 2 tanpa melihat sama sekali elemen array. Oleh karena itu O (n).

PS. Karena persyaratan berubah, periksa perpustakaan Anda untuk mengetahui apa yang tersedia. Di macOS / iOS, Anda membuat NSCountedSet, tambahkan semua angka dari array 2, hapus semua angka dari array 1, dan yang tersisa adalah semua yang ada di array 2 tetapi tidak di array 1, tanpa bergantung pada klaim bahwa ada satu tambahan barang.

var terpendek, terpanjang;

Konversi terpendek ke peta untuk referensi cepat dan lompatan terlama hingga nilai saat ini tidak ada di peta.

Sesuatu seperti ini di javascript:

if (arr1.length> arr2.length) {shortest = arr2; terpanjang = arr1; } else {terpendek = arr1; terpanjang = arr2; }

var map = shortest.reduce (fungsi (obj, nilai) {obj [value] = true; return obj;}, {});

var difference = longest.find (fungsi (nilai) {return !!! map [value];});

O (N) solusi dalam kompleksitas waktu O (1) dalam hal kompleksitas ruang

Pernyataan masalah: Dengan asumsi bahwa array2 berisi semua elemen dari array1 ditambah satu elemen lainnya tidak ada dalam array1.

Solusinya adalah: Kami menggunakan xor untuk menemukan elemen yang tidak ada di array1 jadi langkah-langkahnya adalah: 1. Mulai dari array1 dan lakukan xor dari semua elemen dan simpan dalam variabel. 2. Ambil array2 dan lakukan xor dari semua elemen dengan variabel yang menyimpan xor dari array1. 3. Setelah melakukan operasi, variabel kita akan berisi elemen yang hanya ada di array2. Algoritma di atas berfungsi karena properti berikut dari xor "a xor a = 0" "a xor 0 = a" Saya harap ini menyelesaikan masalah Anda. Juga solusi yang disarankan di atas juga baik-baik saja