Pertanyaan wawancara yang mudah menjadi semakin sulit: angka yang diberikan 1..100, cari nomor yang hilang yang diberikan persis k yang hilang

Saya memiliki pengalaman wawancara kerja yang menarik beberapa waktu lalu. Pertanyaannya dimulai dengan sangat mudah:

Q1 : Kami memiliki tas berisi nomor 1, 2, 3, ..., 100. Setiap angka muncul tepat sekali, sehingga ada 100 angka. Sekarang satu nomor dipilih secara acak dari tas. Temukan nomor yang hilang.

Saya telah mendengar pertanyaan wawancara ini sebelumnya, tentu saja, jadi saya dengan sangat cepat menjawab di sepanjang baris:

A1 : Nah, jumlah dari angka-angka 1 + 2 + 3 + … + Nitu (N+1)(N/2)(lihat Wikipedia: jumlah deret aritmatika ). Sebab N = 100, jumlahnya adalah 5050.

Jadi, jika semua angka ada di dalam tas, jumlahnya akan tepat 5050. Karena satu nomor hilang, jumlahnya akan kurang dari ini, dan perbedaannya adalah angka itu. Jadi kita dapat menemukan nomor yang hilang dalam ruang O(N)dan waktu O(1).

Pada titik ini saya pikir saya telah melakukannya dengan baik, tetapi tiba-tiba pertanyaan itu berubah secara tak terduga:

T2 : Itu benar, tapi sekarang bagaimana Anda melakukan ini jika DUA nomor tidak ada?

Saya belum pernah melihat / mendengar / mempertimbangkan variasi ini sebelumnya, jadi saya panik dan tidak bisa menjawab pertanyaan. Pewawancara bersikeras mengetahui proses pemikiran saya, jadi saya menyebutkan bahwa mungkin kita bisa mendapatkan lebih banyak informasi dengan membandingkan produk yang diharapkan, atau mungkin melakukan pass kedua setelah mengumpulkan beberapa informasi dari pass pertama, dll, tetapi saya benar-benar hanya menembak dalam gelap daripada benar-benar memiliki jalan yang jelas ke solusinya.

Pewawancara memang mencoba mendorong saya dengan mengatakan bahwa memiliki persamaan kedua memang merupakan salah satu cara untuk menyelesaikan masalah. Pada titik ini saya agak kesal (karena tidak mengetahui jawaban sebelumnya), dan bertanya apakah ini adalah teknik pemrograman umum (baca: "berguna"), atau apakah itu hanya trik / jawaban gotcha.

Jawaban pewawancara mengejutkan saya: Anda dapat menggeneralisasi teknik untuk menemukan 3 angka yang hilang. Bahkan, Anda dapat menggeneralisasikannya untuk menemukan k nomor yang hilang.

Qk : Jika nomor k benar -benar hilang dari tas, bagaimana Anda menemukannya secara efisien?

Ini beberapa bulan yang lalu, dan saya masih tidak tahu apa teknik ini. Jelas ada Ω(N)waktu batas bawah karena kita harus memindai semua angka setidaknya sekali, tetapi pewawancara bersikeras bahwa WAKTU dan SPACE kompleksitas teknik pemecahan (minus O(N)waktu scan input) didefinisikan dalam k tidak N .

Jadi pertanyaannya di sini sederhana:

• Bagaimana Anda memecahkan Q2 ?
• Bagaimana Anda memecahkan Q3 ?
• Bagaimana Anda memecahkan Qk ?

Klarifikasi

• Secara umum ada N angka dari 1 .. N , bukan hanya 1..100.
• Saya tidak mencari solusi berbasis set yang jelas, misalnya menggunakan bit set , mengkodekan ada / tidaknya setiap angka dengan nilai bit yang ditunjuk, oleh karena itu menggunakan O(N)bit dalam ruang tambahan. Kita tidak bisa setiap ruang tambahan sebanding dengan N .
• Saya juga tidak mencari pendekatan sort-first yang jelas. Ini dan pendekatan berbasis set layak disebutkan dalam wawancara (mudah diimplementasikan, dan tergantung pada N , bisa sangat praktis). Saya mencari solusi Holy Grail (yang mungkin atau mungkin tidak praktis untuk diterapkan, tetapi memiliki karakteristik asimptotik yang diinginkan).

Jadi sekali lagi, tentu saja Anda harus memindai input O(N), tetapi Anda hanya dapat menangkap sejumlah kecil informasi (didefinisikan sebagai k bukan N ), dan kemudian harus menemukan k angka yang hilang entah bagaimana.

Berikut ringkasan tautan Dimitris Andreou .

Ingat jumlah kekuatan ke-i, di mana i = 1,2, .., k. Ini mengurangi masalah untuk menyelesaikan sistem persamaan

a ₁ + a ₂ + ... + a _k = b ₁

a ₁ ² + a ₂ ² + ... + a _k ² = b ₂

...

a ₁ ^k + a ₂ ^k + ... + a _k ^k = b _k

Menggunakan identitas Newton , mengetahui b _i memungkinkan untuk menghitung

c ₁ = a ₁ + a ₂ + ... a _k

c ₂ = a ₁ a ₂ + a ₁ a ₃ + ... + a _k-1 a _k

...

c _k = a ₁ a ₂ ... a _k

Jika Anda memperluas polinomial (xa ₁ ) ... (xa _k ) koefisiennya akan persis c ₁ , ..., c _k - lihat formula Viète . Karena setiap faktor polinomial unik (ring polinomial adalah domain Euclidean ), ini berarti _i ditentukan secara unik, hingga permutasi.

Ini mengakhiri bukti bahwa daya ingat sudah cukup untuk memulihkan angka. Untuk konstanta k, ini adalah pendekatan yang baik.

Namun, ketika k bervariasi, pendekatan langsung dari komputasi c ₁ , ..., _ck sangat mahal, karena _ck adalah produk dari semua angka yang hilang, besarnya n! / (Nk) !. Untuk mengatasinya, lakukan perhitungan dalam bidang _Zq , di mana q adalah bilangan prima sehingga n <= q <2n - itu ada oleh postulat Bertrand . Buktinya tidak perlu diubah, karena rumus masih berlaku, dan faktorisasi polinomial masih unik. Anda juga memerlukan algoritme untuk faktorisasi bidang terbatas, misalnya yang dilakukan oleh Berlekamp atau Cantor-Zassenhaus .

Pseudocode tingkat tinggi untuk k konstan:

• Hitung kekuatan ke-i dari angka yang diberikan
• Kurangi untuk mendapatkan jumlah kekuatan ke-i dari angka yang tidak diketahui. Panggil penjumlahannya b _i .
• Gunakan identitas Newton untuk menghitung koefisien dari b _i ; panggil mereka c _i . Pada dasarnya, c ₁ = b ₁ ; c ₂ = (c ₁ b ₁ - b ₂ ) / 2; lihat Wikipedia untuk formula yang tepat
• Faktor polinomial x ^k -c ₁ x ^k-1 + ... + c _k .
• Akar polinomial adalah angka yang dibutuhkan a ₁ , ..., a _k .

Untuk memvariasikan k, temukan bilangan prima n <= q <2n menggunakan misal Miller-Rabin, dan lakukan langkah-langkah dengan semua bilangan dikurangi modulo q.

EDIT: Versi sebelumnya dari jawaban ini menyatakan bahwa alih-alih Z _q , di mana q adalah prima, dimungkinkan untuk menggunakan bidang hingga dengan karakteristik 2 (q = 2 ^ (log n)). Ini tidak terjadi, karena rumus Newton memerlukan pembagian dengan angka hingga k.

Anda akan menemukannya dengan membaca beberapa halaman Muthukrishnan - Algoritma Aliran Data: Teka-teki 1: Menemukan Angka yang Hilang . Ini menunjukkan persis generalisasi yang Anda cari . Mungkin inilah yang pewawancara Anda baca dan mengapa ia mengajukan pertanyaan-pertanyaan ini.

Sekarang, jika hanya orang yang akan mulai menghapus jawaban yang dimasukkan atau diganti oleh perlakuan Muthukrishnan, dan membuat teks ini lebih mudah ditemukan. :)

Lihat juga jawaban terkait langsung sdcvvc , yang juga termasuk pseudocode (hore! Tidak perlu membaca formulasi matematika yang rumit :)) (terima kasih, kerja bagus!).

Kita dapat memecahkan Q2 dengan menjumlahkan kedua angka itu sendiri, dan kuadrat dari angka tersebut.

Kami kemudian dapat mengurangi masalah menjadi

k1 + k2 = x
k1^2 + k2^2 = y

Di mana xdan yseberapa jauh jumlahnya di bawah nilai yang diharapkan.

Pengganti memberi kita:

(x-k2)^2 + k2^2 = y

Yang kemudian bisa kita pecahkan untuk menentukan nomor kita yang hilang.

Seperti yang ditunjukkan oleh @j_random_hacker, ini sangat mirip dengan Menemukan duplikat dalam ruang O (n) dan O (1) , dan adaptasi jawaban saya di sana juga berfungsi di sini.

Dengan asumsi bahwa "tas" diwakili oleh array A[]ukuran 1 berbasis N - k, kita dapat menyelesaikan Qk dalam O(N)waktu danO(k) ruang tambahan.

Pertama, kita perluas array kita A[]dengan kelemen, sehingga ukurannya sekarang N. Ini adalah O(k)ruang tambahan. Kami kemudian menjalankan algoritma kode semu berikut:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

Loop pertama menginisialisasi kentri tambahan ke sama dengan entri pertama dalam array (ini hanya nilai nyaman yang kita tahu sudah ada dalam array - setelah langkah ini, setiap entri yang hilang dalam array ukuran awalN-k adalah masih hilang dalam array yang diperluas).

Loop kedua memungkinkan array diperluas sehingga jika elemen xhadir setidaknya satu kali, maka salah satu entri tersebut akan berada pada posisiA[x] .

Perhatikan bahwa meskipun memiliki loop bersarang, ia masih berjalan dalam O(N)waktu - swap hanya terjadi jika ada isedemikian rupa A[i] != i, dan setiap swap menetapkan setidaknya satu elemen sedemikian rupa A[i] == i, di mana itu tidak benar sebelumnya. Ini berarti bahwa jumlah total swap (dan dengan demikian jumlah total eksekusi dari whileloop body) paling banyak N-1.

Loop ketiga mencetak indeks-indeks array iyang tidak ditempati oleh nilai i- ini berarti yang ipasti telah hilang.

Saya meminta seorang anak berusia 4 tahun untuk menyelesaikan masalah ini. Dia mengurutkan angka dan kemudian menghitung. Ini memiliki persyaratan ruang O (lantai dapur), dan itu bekerja dengan mudah namun banyak bola yang hilang.

Tidak yakin, apakah ini solusi yang paling efisien, tetapi saya akan mengulang semua entri, dan menggunakan bitet untuk mengingat, angka mana yang ditetapkan, dan kemudian menguji 0 bit.

Saya suka solusi sederhana - dan saya bahkan percaya, bahwa mungkin lebih cepat daripada menghitung jumlah, atau jumlah kotak, dll.

Saya belum memeriksa matematika, tetapi saya menduga bahwa menghitung Σ(n^2)dalam kode yang sama seperti yang kita hitung Σ(n)akan memberikan informasi yang cukup untuk mendapatkan dua angka yang hilang, Lakukan Σ(n^3)juga jika ada tiga, dan seterusnya.

Masalah dengan solusi berdasarkan jumlah angka adalah mereka tidak memperhitungkan biaya penyimpanan dan bekerja dengan angka dengan eksponen besar ... dalam praktiknya, agar dapat bekerja untuk n yang sangat besar, perpustakaan angka besar akan digunakan . Kita dapat menganalisis pemanfaatan ruang untuk algoritma ini.

Kita dapat menganalisis kompleksitas ruang dan waktu dari algoritma sdcvvc dan Dimitris Andreou.

Penyimpanan:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

Begitu l_j \in \Theta(j log n)

Total penyimpanan yang digunakan: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Ruang yang digunakan: dengan asumsi bahwa komputasi a^jmembutuhkan ceil(log_2 j)waktu, total waktu:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Total waktu yang digunakan: \Theta(kn log n)

Jika waktu dan ruang ini memuaskan, Anda dapat menggunakan algoritma rekursif sederhana. Biarkan b! I menjadi entri ke-i di tas, n jumlah angka sebelum pemindahan, dan k jumlah pemindahan. Dalam sintaksis Haskell ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Penyimpanan yang digunakan: O(k)untuk daftar, O(log(n))untuk tumpukan: O(k + log(n)) Algoritma ini lebih intuitif, memiliki kompleksitas waktu yang sama, dan menggunakan lebih sedikit ruang.

Tunggu sebentar. Seperti yang dinyatakan pertanyaan, ada 100 nomor di dalam tas. Tidak peduli seberapa besar k, masalah dapat diselesaikan dalam waktu yang konstan karena Anda dapat menggunakan satu set dan menghapus angka dari set di paling banyak 100 - iterasi loop. 100 konstan. Himpunan angka yang tersisa adalah jawaban Anda.

Jika kita menggeneralisasi solusi ke angka dari 1 ke N, tidak ada yang berubah kecuali N bukan konstanta, jadi kita berada dalam O (N - k) = O (N) waktu. Misalnya, jika kita menggunakan set bit, kita mengatur bit ke 1 dalam waktu O (N), beralih melalui angka, mengatur bit ke 0 saat kita pergi (O (Nk) = O (N)) dan kemudian kita punya jawabannya.

Tampak bagi saya bahwa pewawancara bertanya kepada Anda bagaimana mencetak isi set terakhir dalam waktu O (k) daripada waktu O (N). Jelas, dengan set bit, Anda harus mengulangi semua N bit untuk menentukan apakah Anda harus mencetak nomor atau tidak. Namun, jika Anda mengubah cara set diimplementasikan, Anda dapat mencetak angka dalam iterasi. Ini dilakukan dengan memasukkan angka-angka ke dalam objek yang akan disimpan dalam hash set dan daftar tertaut ganda. Saat Anda menghapus objek dari kumpulan hash, Anda juga menghapusnya dari daftar. Jawabannya akan ditinggalkan dalam daftar yang panjangnya sekarang k.

Untuk memecahkan 2 (dan 3) pertanyaan angka yang hilang, Anda dapat memodifikasi quickselect, yang rata-rata berjalan O(n)dan menggunakan memori konstan jika partisi dilakukan di tempat.

1. Partisi himpunan sehubungan dengan pivot acak pke dalam partisi l, yang berisi angka lebih kecil dari pivot, dan r, yang berisi angka lebih besar dari pivot.

2. Tentukan di partisi mana 2 angka yang hilang berada dengan membandingkan nilai pivot dengan ukuran setiap partisi ( p - 1 - count(l) = count of missing numbers in ldan n - count(r) - p = count of missing numbers in r)

3. a) Jika setiap partisi kehilangan satu nomor, gunakan pendekatan perbedaan jumlah untuk menemukan setiap nomor yang hilang.

   (1 + 2 + ... + (p-1)) - sum(l) = missing #1 dan ((p+1) + (p+2) ... + n) - sum(r) = missing #2

   b) Jika satu partisi kehilangan kedua angka dan partisi kosong, maka angka yang hilang adalah salah satu (p-1,p-2)atau (p+1,p+2) tergantung pada partisi mana yang kehilangan angka.

   Jika satu partisi kehilangan 2 angka tetapi tidak kosong, maka kembalilah ke partiton itu.

Dengan hanya 2 angka yang hilang, algoritme ini selalu membuang setidaknya satu partisi, sehingga mempertahankan O(n)kompleksitas waktu rata-rata pemilihan cepat. Demikian pula, dengan 3 angka yang hilang, algoritma ini juga membuang setidaknya satu partisi dengan setiap pass (karena seperti dengan 2 angka yang hilang, paling banyak hanya 1 partisi yang akan mengandung beberapa angka yang hilang). Namun, saya tidak yakin seberapa banyak kinerja menurun ketika lebih banyak angka yang hilang ditambahkan.

Berikut ini adalah implementasi yang tidak menggunakan partisi di tempat, jadi contoh ini tidak memenuhi persyaratan ruang tetapi menggambarkan langkah-langkah algoritma:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Demo

Inilah solusi yang menggunakan k bit penyimpanan ekstra, tanpa trik pintar dan langsung. Waktu eksekusi O (n), ruang ekstra O (k). Hanya untuk membuktikan bahwa ini dapat diselesaikan tanpa membaca solusinya terlebih dahulu atau menjadi jenius:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

Bisakah Anda memeriksa apakah setiap nomor ada? Jika ya, Anda dapat mencoba ini:

S = jumlah semua angka dalam kantung (S <5050)
Z = jumlah angka yang hilang 5050 - S

jika nomor yang hilang adalah xdan ykemudian:

x = Z - y dan
maks (x) = Z - 1

Jadi, Anda memeriksa rentang dari 1ke max(x)dan menemukan nomornya

Mungkin algoritma ini dapat berfungsi untuk pertanyaan 1:

1. Precorute xor dari 100 integer pertama (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
2. xor elemen-elemen karena mereka terus datang dari input stream (val1 = val1 ^ next_input)
3. jawaban akhir = val ^ val1

Atau lebih baik lagi:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

Algoritma ini sebenarnya dapat diperluas untuk dua nomor yang hilang. Langkah pertama tetap sama. Ketika kita memanggil GetValue dengan dua angka yang hilang, hasilnya a1^a2adalah dua angka yang hilang. Katakanlah

val = a1^a2

Sekarang untuk menyaring a1 dan a2 dari val kita mengambil bit yang telah ditentukan di val. Katakanlah ithbit diatur dalam val. Itu berarti a1 dan a2 memiliki paritas yang berbeda pada ithposisi bit. Sekarang kita lakukan iterasi lain pada array asli dan menyimpan dua nilai xor. Satu untuk angka-angka yang memiliki bit set ith dan lainnya yang tidak memiliki bit set ith. Kami sekarang memiliki dua ember angka, dan dijamin bahwa itu a1 and a2akan terletak pada ember yang berbeda. Sekarang ulangi hal yang sama dengan yang kami lakukan untuk menemukan satu elemen yang hilang pada masing-masing ember.

Anda dapat memecahkan Q2 jika Anda memiliki jumlah dari kedua daftar dan produk dari kedua daftar.

(l1 adalah yang asli, l2 adalah daftar yang dimodifikasi)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

Kami dapat mengoptimalkan ini karena jumlah dari rangkaian aritmatika adalah n kali rata-rata istilah pertama dan terakhir:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Sekarang kita tahu bahwa (jika a dan b adalah angka yang dihapus):

a + b = d
a * b = m

Jadi kita dapat mengatur ulang ke:

a = s - b
b * (s - b) = m

Dan gandakan:

-b^2 + s*b = m

Dan mengatur ulang sehingga sisi kanan adalah nol:

-b^2 + s*b - m = 0

Maka kita bisa menyelesaikannya dengan rumus kuadratik:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Contoh kode Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

Saya tidak tahu kerumitan fungsi sqrt, pengurangan dan penjumlahan jadi saya tidak dapat menghitung kompleksitas solusi ini (jika ada yang tahu, silakan komentar di bawah.)

Untuk Q2 ini adalah solusi yang sedikit lebih tidak efisien daripada yang lain, tetapi masih memiliki runtime O (N) dan membutuhkan ruang O (k).

Idenya adalah menjalankan algoritma asli dua kali. Di yang pertama Anda mendapatkan jumlah total yang hilang, yang memberi Anda batas atas dari angka yang hilang. Sebut saja nomor ini N. Anda tahu bahwa dua angka yang hilang akan dijumlahkan N, jadi angka pertama hanya bisa berada dalam interval [1, floor((N-1)/2)]sementara yang kedua akan masuk [floor(N/2)+1,N-1].

Dengan demikian Anda mengulang semua angka sekali lagi, membuang semua angka yang tidak termasuk dalam interval pertama. Yang ada, Anda melacak jumlah mereka. Akhirnya, Anda akan tahu salah satu dari dua angka yang hilang, dan dengan ekstensi yang kedua.

Saya merasa bahwa metode ini dapat digeneralisasi dan mungkin beberapa pencarian berjalan secara "paralel" selama satu kali masukan, tetapi saya belum menemukan caranya.

Saya pikir ini dapat dilakukan tanpa persamaan dan teori matematika yang kompleks. Di bawah ini adalah proposal untuk solusi kompleksitas tempat dan O (2n):

Asumsi formulir input:

# angka dalam tas = n

# angka yang hilang = k

Angka-angka dalam tas diwakili oleh array panjang

Panjang array input untuk algo = n

Entri yang hilang dalam array (angka yang dikeluarkan dari kantong) diganti dengan nilai elemen pertama dalam array.

Misalnya. Awalnya tas terlihat seperti [2,9,3,7,8,6,4,5,1,10]. Jika 4 dikeluarkan, nilai 4 akan menjadi 2 (elemen pertama dari array). Karenanya setelah mengeluarkan 4 tas akan terlihat seperti [2,9,3,7,8,6,2,5,1,10]

Kunci dari solusi ini adalah untuk menandai INDEX dari nomor yang dikunjungi dengan meniadakan nilai pada INDEX itu ketika array dilintasi.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

Ada cara umum untuk menggeneralisasi algoritma streaming seperti ini. Idenya adalah untuk menggunakan sedikit pengacakan untuk semoga 'menyebar' kelemen ke dalam sub masalah independen, di mana algoritma asli kami memecahkan masalah bagi kami. Teknik ini digunakan dalam rekonstruksi sinyal jarang, antara lain.

• Buat sebuah array,, dengan aukuran u = k^2.
• Memilih setiap fungsi hash yang universal , h : {1,...,n} -> {1,...,u}. (Seperti multiply-shift )
• Untuk setiap idi 1, ..., npeningkatana[h(i)] += i
• Untuk setiap angka xdalam aliran input, pengurangan a[h(x)] -= x.

Jika semua angka yang hilang telah di hash ke kotak berbeda, elemen bukan nol dari array sekarang akan berisi angka yang hilang.

Probabilitas bahwa pasangan tertentu dikirim ke keranjang yang sama, kurang dari 1/udefinisi fungsi hash universal. Karena ada tentang k^2/2pasangan, kami memiliki probabilitas kesalahan paling banyak k^2/2/u=1/2. Artinya, kami berhasil dengan probabilitas setidaknya 50%, dan jika kami meningkatkan ukami meningkatkan peluang kami.

Perhatikan bahwa algoritma ini membutuhkan k^2 lognbit ruang (Kita perlu lognbit per array ember.) Ini cocok dengan ruang yang diperlukan oleh jawaban @ Dimitris Andreou (Khususnya persyaratan ruang faktorisasi polinomial, yang kebetulan juga diacak.) Algoritma ini juga memiliki konstanta waktu per pembaruan, bukan waktu kdalam hal jumlah daya.

Bahkan, kita bisa lebih efisien daripada metode jumlah daya dengan menggunakan trik yang dijelaskan dalam komentar.

Solusi yang sangat sederhana untuk Q2 yang saya terkejut tidak ada yang menjawab. Gunakan metode dari Q1 untuk menemukan jumlah dari dua angka yang hilang. Mari kita sebutkan dengan S, maka salah satu angka yang hilang lebih kecil dari S / 2 dan yang lainnya lebih besar dari S / 2 (duh). Jumlahkan semua angka dari 1 hingga S / 2 dan bandingkan dengan hasil rumus (mirip dengan metode pada Q1) untuk menemukan yang lebih rendah di antara angka yang hilang. Kurangi dari S untuk menemukan angka hilang yang lebih besar.

Masalah yang sangat bagus Saya akan menggunakan perbedaan set untuk Qk. Banyak bahasa pemrograman bahkan memiliki dukungan untuk itu, seperti di Ruby:

missing = (1..100).to_a - bag

Ini mungkin bukan solusi yang paling efisien tapi itu salah satu yang akan saya gunakan dalam kehidupan nyata jika saya dihadapkan dengan tugas seperti itu dalam kasus ini (batas yang diketahui, batas rendah). Jika himpunan bilangan akan sangat besar maka saya akan mempertimbangkan algoritma yang lebih efisien, tentu saja, tetapi sampai saat itu solusi sederhana akan cukup bagi saya.

Anda dapat mencoba menggunakan Bloom Filter . Masukkan setiap nomor dalam kantong ke dalam mekar, lalu ulangi set lengkap 1-k sampai melaporkan masing-masing yang tidak ditemukan. Ini mungkin tidak menemukan jawabannya di semua skenario, tetapi mungkin merupakan solusi yang cukup baik.

Saya akan mengambil pendekatan berbeda untuk pertanyaan itu dan menyelidiki pewawancara untuk rincian lebih lanjut tentang masalah yang lebih besar yang dia coba selesaikan. Bergantung pada masalah dan persyaratan yang mengelilinginya, solusi berbasis set yang jelas mungkin adalah hal yang benar dan pendekatan menghasilkan-daftar-dan-memilih-melalui-itu-sesudahnya mungkin tidak.

Sebagai contoh, mungkin pewawancara akan mengirim npesan dan perlu tahu kyang tidak menghasilkan balasan dan perlu mengetahuinya sesedikit mungkin jam dinding setelah n-kbalasan th tiba. Katakan juga bahwa sifat saluran pesan sedemikian rupa sehingga bahkan berjalan dengan kecepatan penuh, ada cukup waktu untuk melakukan beberapa pemrosesan antar pesan tanpa berdampak pada berapa lama waktu yang diperlukan untuk menghasilkan hasil akhir setelah balasan terakhir tiba. Waktu itu dapat digunakan untuk memasukkan beberapa aspek identifikasi dari setiap pesan yang dikirim ke set dan menghapusnya ketika setiap balasan yang sesuai tiba. Setelah balasan terakhir tiba, satu-satunya hal yang harus dilakukan adalah menghapus pengenalnya dari set, yang biasanya membutuhkan implementasiO(log k+1). Setelah itu, set berisi daftar kelemen yang hilang dan tidak ada proses tambahan yang harus dilakukan.

Ini tentu bukan pendekatan tercepat untuk pemrosesan batch jumlah tas yang dibuat sebelumnya karena semuanya berjalan O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Tapi itu bekerja untuk nilai apa pun k(bahkan jika itu tidak diketahui sebelumnya) dan dalam contoh di atas diterapkan dengan cara yang meminimalkan interval paling kritis.

Anda dapat memotivasi solusi dengan memikirkannya dalam hal simetri (kelompok, dalam bahasa matematika). Tidak peduli urutan himpunan angka, jawabannya harus sama. Jika Anda akan menggunakan kfungsi untuk membantu menentukan elemen yang hilang, Anda harus memikirkan fungsi apa yang memiliki properti itu: simetris. Fungsi s_1(x) = x_1 + x_2 + ... + x_nini adalah contoh dari fungsi simetris, tetapi ada yang lain dari tingkat yang lebih tinggi. Secara khusus, perhatikan fungsi simetris dasar . Fungsi simetris dasar derajat 2 adalah s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n, jumlah dari semua produk dari dua elemen. Demikian pula untuk fungsi simetris dasar derajat 3 dan lebih tinggi. Mereka jelas simetris. Selanjutnya, ternyata mereka adalah blok bangunan untuk semua fungsi simetris.

Anda dapat membangun fungsi simetris dasar saat Anda memerhatikannya s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Pemikiran lebih lanjut harus meyakinkan Anda itu s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))dan seterusnya, sehingga mereka dapat dihitung dalam satu pass.

Bagaimana cara mengetahui item mana yang hilang dari array? Pikirkan tentang jumlahnya banyak (z-x_1)(z-x_2)...(z-x_n). Ini mengevaluasi 0jika Anda memasukkan salah satu nomor x_i. Memperluas jumlahnya banyak, Anda dapatkan z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Fungsi simetris dasar juga muncul di sini, yang benar-benar tidak mengejutkan, karena polinom harus tetap sama jika kita menerapkan permutasi ke akar.

Jadi kita dapat membangun polinomial dan mencoba memfaktorkannya untuk mencari tahu angka mana yang tidak ada dalam set, seperti yang telah disebutkan orang lain.

Akhirnya, jika kita khawatir tentang meluap memori dengan jumlah besar (polinomial simetris ke-n adalah urutan 100!), kita dapat melakukan perhitungan ini di mod pmana pbilangan prima lebih besar dari 100. Dalam hal ini kita mengevaluasi polinomial mod pdan menemukan bahwa itu mengevaluasi lagi untuk 0saat input adalah angka di set, dan mengevaluasi ke nilai non-nol ketika input adalah angka tidak di set. Namun, seperti yang telah ditunjukkan orang lain, untuk mendapatkan nilai dari polinomial dalam waktu yang tergantung k, tidak N, kita harus memperhitungkan polinomial mod p.

Namun cara lain adalah menggunakan penyaringan grafik residual.

Misalkan kita memiliki angka 1 hingga 4 dan 3 tidak ada. Representasi biner adalah sebagai berikut,

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

Dan saya bisa membuat diagram alur seperti berikut ini.

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

Perhatikan bahwa grafik aliran berisi x node, sementara x menjadi jumlah bit. Dan jumlah tepi maksimum adalah (2 * x) -2.

Jadi untuk integer 32 bit akan membutuhkan ruang O (32) atau O (1).

Sekarang jika saya menghapus kapasitas untuk masing-masing angka mulai dari 1,2,4 maka saya dibiarkan dengan grafik sisa.

0 ----------> 1 ---------> 1

Akhirnya saya akan menjalankan loop seperti berikut ini,

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Sekarang hasilnya adalah resultberisi angka-angka yang tidak hilang juga (false positive). Tetapi k <= (ukuran hasilnya) <= n ketika ada kelemen yang hilang.

Saya akan memeriksa daftar yang diberikan untuk terakhir kali untuk menandai hasil yang hilang atau tidak.

Jadi kompleksitas waktu adalah O (n).

Akhirnya, adalah mungkin untuk mengurangi jumlah positif palsu (dan ruang yang dibutuhkan) dengan mengambil node 00, 01, 11, 10bukan hanya 0dan 1.

Anda mungkin perlu klarifikasi tentang arti O (k).

Ini solusi sepele untuk arbitrary k: untuk setiap v dalam set angka Anda, kumpulkan jumlah 2 ^ v. Pada akhirnya, loop i dari 1 ke N. Jika jumlah bitwise ANDed dengan 2 ^ i adalah nol, maka saya hilang. (Atau secara numerik, jika jumlah lantai dibagi 2 ^ i adalah genap. Atau sum modulo 2^(i+1)) < 2^i.)

Mudah kan? O (N) waktu, O (1) penyimpanan, dan mendukung sewenang-wenang k.

Kecuali bahwa Anda menghitung angka besar yang pada komputer nyata masing-masing akan membutuhkan ruang O (N). Bahkan, solusi ini identik dengan vektor sedikit.

Jadi Anda bisa menjadi pintar dan menghitung jumlah dan jumlah kotak dan jumlah kubus ... hingga jumlah v ^ k, dan melakukan matematika mewah untuk mengekstraksi hasilnya. Tetapi itu juga angka besar, yang menimbulkan pertanyaan: model operasi abstrak apa yang sedang kita bicarakan? Seberapa cocok dalam O (1) ruang, dan berapa lama waktu yang dibutuhkan untuk merangkum jumlah ukuran apa pun yang Anda butuhkan?

Ini adalah solusi yang tidak bergantung pada matematika kompleks seperti jawaban sdcvvc / Dimitris Andreou, tidak mengubah array input seperti yang dilakukan caf dan Kolonel Panic, dan tidak menggunakan bitset ukuran besar seperti Chris Lercher, JeremyP dan banyak yang melakukannya. Pada dasarnya, saya mulai dengan ide Svalorzen / Gilad Deutch untuk Q2, menggeneralisasikannya ke kasus umum Qk dan diimplementasikan di Jawa untuk membuktikan bahwa algoritme berfungsi.

Ide

Misalkan kita memiliki interval I arbitrer yang kita hanya tahu bahwa itu mengandung setidaknya satu dari angka yang hilang. Setelah satu lulus melalui array masukan, hanya melihat angka-angka dari saya , kita dapat memperoleh baik jumlah S dan kuantitas Q hilang nomor dari saya . Kami melakukan ini dengan hanya decrementing I panjang setiap kali kita jumpai nomor dari saya (untuk memperoleh Q ) dan dengan mengurangi pra-dihitung jumlah semua nomor di I dengan nomor ditemui setiap kali (untuk memperoleh S ).

Sekarang kita melihat S dan Q . Jika Q = 1 , itu berarti bahwa kemudian saya hanya berisi salah satu nomor yang hilang, dan jumlah ini jelas S . Kami menandai saya sebagai selesai (disebut "tidak ambigu" dalam program ini) dan meninggalkannya dari pertimbangan lebih lanjut. Di sisi lain, jika Q> 1 , kita dapat menghitung rata-rata A = S / Q nomor hilang terkandung dalam saya . Seperti semua nomor yang berbeda, setidaknya satu dari nomor tersebut secara ketat kurang dari A dan setidaknya satu ketat lebih besar dari A . Sekarang kita membagi saya di Amenjadi dua interval yang lebih kecil yang masing-masing berisi setidaknya satu nomor yang hilang. Perhatikan bahwa tidak masalah ke interval mana yang kami tetapkan A jika itu adalah bilangan bulat.

Kami membuat larik array berikutnya menghitung S dan Q untuk masing-masing interval secara terpisah (tetapi dalam lintasan yang sama) dan setelah itu menandai interval dengan Q = 1 dan membagi interval dengan Q> 1 . Kami melanjutkan proses ini sampai tidak ada interval "ambigu" baru, yaitu kami tidak memiliki apa-apa untuk dibagi karena setiap interval mengandung tepat satu nomor yang hilang (dan kami selalu tahu nomor ini karena kami tahu S ). Kita mulai dari satu-satunya interval "seluruh rentang" yang berisi semua angka yang mungkin (seperti [1..N] dalam pertanyaan).

Analisis kompleksitas waktu dan ruang

Jumlah lintasan p yang perlu kita buat sampai proses berhenti tidak pernah lebih besar dari jumlah angka yang hilang k . Ketidaksetaraan p <= k dapat dibuktikan dengan ketat. Di sisi lain, ada juga batas atas empiris p <log ₂ N + 3 yang berguna untuk nilai besar k . Kita perlu melakukan pencarian biner untuk setiap nomor array input untuk menentukan interval miliknya. Ini menambah pengali log k ke kompleksitas waktu.

Secara total, kompleksitas waktu adalah O (N ᛫ min (k, log N) ᛫ log k) . Perhatikan bahwa untuk k besar , ini jauh lebih baik daripada metode sdcvvc / Dimitris Andreou, yaitu O (N ᛫ k) .

Untuk pekerjaannya, algoritma ini membutuhkan O (k) ruang tambahan untuk menyimpan pada interval paling k , yang secara signifikan lebih baik daripada O (N) dalam solusi "bitset".

Implementasi Java

Berikut adalah kelas Java yang mengimplementasikan algoritma di atas. Selalu mengembalikan diurutkan array nomor hilang. Selain itu, tidak memerlukan angka yang hilang, hitung k karena menghitungnya pada pass pertama. Seluruh rentang angka diberikan oleh parameter minNumberdan maxNumber(misalnya 1 dan 100 untuk contoh pertama dalam pertanyaan).

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

Untuk keadilan, kelas ini menerima input dalam bentuk NumberBagobjek. NumberBagtidak mengizinkan modifikasi larik dan akses acak dan juga menghitung berapa kali larik diminta untuk melintasi sekuensial. Ini juga lebih cocok untuk pengujian array besar daripada Iterable<Integer>karena menghindari tinju intnilai-nilai primitif dan memungkinkan membungkus sebagian besar int[]untuk persiapan pengujian yang nyaman. Tidak sulit untuk mengganti, jika diinginkan, NumberBagdengan int[]atau Iterable<Integer>mengetikkan findtanda tangan, dengan mengubah dua for-loop di dalamnya menjadi masing-masing.

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

Tes

Contoh sederhana yang menunjukkan penggunaan kelas-kelas ini diberikan di bawah ini.

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

Pengujian array besar dapat dilakukan dengan cara ini:

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Cobalah di Ideone

Saya yakin saya memiliki algoritma ruang O(k)dan waktu O(log(k)), mengingat Anda memiliki floor(x)dan log2(x)fungsi untuk bilangan bulat besar yang tersedia:

Anda memiliki kbilangan bulat panjang-bit (karena itu log8(k)ruang) tempat Anda menambahkan x^2, di mana x adalah angka berikutnya yang Anda temukan dalam tas: s=1^2+2^2+...Ini membutuhkan O(N)waktu (yang tidak menjadi masalah bagi pewawancara). Pada akhirnya Anda mendapatkan j=floor(log2(s))yang merupakan jumlah terbesar yang Anda cari. Kemudian s=s-jdan Anda lakukan lagi di atas:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Sekarang, Anda biasanya tidak memiliki fungsi lantai dan log2 untuk 2756bilangan bulat-bit tetapi bukan untuk ganda. Begitu? Sederhananya, untuk setiap 2 byte (atau 1, atau 3, atau 4) Anda dapat menggunakan fungsi-fungsi ini untuk mendapatkan angka yang diinginkan, tetapi ini menambah O(N)faktor kompleksitas waktu

Ini mungkin terdengar bodoh, tetapi, dalam masalah pertama yang disajikan kepada Anda, Anda harus melihat semua angka yang tersisa di tas untuk benar-benar menjumlahkannya untuk menemukan nomor yang hilang menggunakan persamaan itu.

Jadi, karena Anda bisa melihat semua angka, cari saja nomor yang hilang. Hal yang sama berlaku ketika dua nomor hilang. Cukup sederhana menurut saya. Tidak ada gunanya menggunakan persamaan ketika Anda bisa melihat angka yang tersisa di tas.

Saya pikir ini dapat digeneralisasi seperti ini:

Nyatakan S, M sebagai nilai awal untuk jumlah deret aritmatika dan perkalian.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

Saya harus memikirkan rumus untuk menghitung ini, tetapi bukan itu intinya. Lagi pula, jika satu nomor tidak ada, Anda sudah memberikan solusinya. Namun, jika dua angka tidak ada, mari kita tunjukkan jumlah baru dan kelipatan total dengan S1 dan M1, yang akan menjadi sebagai berikut:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Karena Anda tahu S1, M1, M dan S, persamaan di atas dapat dipecahkan untuk menemukan a dan b, angka yang hilang.

Sekarang untuk tiga angka yang hilang:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

Sekarang tidak diketahui Anda adalah 3 sementara Anda hanya memiliki dua persamaan yang dapat Anda pecahkan.

Saya tidak tahu apakah ini efisien atau tidak, tetapi saya ingin menyarankan solusi ini.

1. Hitung xor dari 100 elemen
2. Hitung xor dari 98 elemen (setelah 2 elemen dihapus)
3. Sekarang (hasil dari 1) XOR (hasil dari 2) memberi Anda xor dari dua no yang hilang i..ea XOR b jika a dan b adalah elemen yang hilang
   4. Dapatkan jumlah dari No yang hilang dengan pendekatan biasa Anda dari menjumlahkan rumus diff dan katakanlah diff adalah d.

Sekarang jalankan loop untuk mendapatkan pasangan yang memungkinkan (p, q) yang keduanya terletak pada [1, 100] dan jumlah ke d.

Ketika sepasang diperoleh, periksa apakah (hasil 3) XOR p = q dan jika ya kita selesai.

Harap perbaiki saya jika saya salah dan komentari kompleksitas waktu jika ini benar

Kita dapat melakukan Q1 dan Q2 di O (log n) sebagian besar waktu.

Misalkan kita memory chipterdiri dari array njumlah test tubes. Dan angka xdalam tabung reaksi diwakili oleh x millilitercairan kimia.

Misalkan prosesor kita adalah a laser light. Ketika kita menyalakan laser itu melintasi semua tabung tegak lurus dengan panjangnya. Setiap kali melewati cairan kimia, luminositas berkurang 1. Dan melewati cahaya pada tanda mililiter tertentu adalah operasi O(1).

Sekarang jika kita menyalakan laser kita di tengah tabung reaksi dan mendapatkan hasil luminositas

• sama dengan nilai yang dihitung sebelumnya (dihitung ketika tidak ada angka yang hilang), maka angka yang hilang lebih besar dari n/2.
• Jika output kami lebih kecil, maka setidaknya ada satu nomor yang lebih kecil dari n/2. Kami juga dapat memeriksa apakah luminositas berkurang oleh 1atau 2. jika dikurangi 1maka satu nomor yang hilang lebih kecil dari n/2dan yang lainnya lebih besar dari n/2. Jika dikurangi 2maka kedua angka lebih kecil dari n/2.

Kami dapat mengulangi proses di atas berulang kali mempersempit domain masalah kami. Di setiap langkah, kami membuat domain lebih kecil setengahnya. Dan akhirnya kita bisa mencapai hasil kita.

Algoritma paralel yang layak disebut (karena mereka menarik),

• pengurutan dengan beberapa algoritma paralel, misalnya, penggabungan paralel dapat dilakukan dalam O(log^3 n)waktu. Dan kemudian nomor yang hilang dapat ditemukan oleh pencarian biner pada O(log n)waktunya.
• Secara teoritis, jika kita memiliki nprosesor maka setiap proses dapat memeriksa salah satu input dan mengatur beberapa flag yang mengidentifikasi nomor (dengan mudah dalam sebuah array). Dan pada langkah selanjutnya setiap proses dapat memeriksa setiap bendera dan akhirnya menampilkan nomor yang tidak ditandai. Seluruh proses akan memakan O(1)waktu. Ini memiliki O(n)kebutuhan ruang / memori tambahan .

Perhatikan, bahwa dua algoritma paralel yang disediakan di atas mungkin memerlukan ruang tambahan seperti yang disebutkan dalam komentar .