Asan bir müsahibə ilə sual daha mürəkkəbləşdi: 1..100 rəqəmlərini nəzərə alaraq, itkin sayı (lar)

Bir müddət əvvəl həmsöhbətimlə maraqlı bir müsahibə keçirdim. Sual çox sadə idi:

S1 : 1 , 2 , 3 , ..., 100 nömrələri olan bir çanta var. Hər bir nömrə tam olaraq bir dəfə görünür, buna görə də 100 nömrə. İndi bir ədəd təsadüfi bagdan seçilir. Eksik nömrəni tapın.

Əlbətdə müsahibə əvvəli bu sualı duydum, belə ki tezliklə xəttlərdə cavab verdim:

A1 : yaxşı, 1 + 2 + 3 + … + N ədədinə bərabərdir (N+1)(N/2) (bax Wikipedia: aritmetik seriyanın cəmi ). N = 100 məbləğ 5050 dir.

Beləliklə, bütün ədədlər çanta içərsə, məbləği tam olaraq 5050 olacaqdır. Bir ədəd itkin olduğundan, məbləğ bundan az olacaq və fərq bir sıradır. Beləliklə, itkin sayını O(N) zamanında və O(1) sahədə tapa bilərsiniz.

O anda müvəffəqiyyətli olduğumu düşündüm, ancaq birdən soruşdu:

S2 : Bu doğru, amma indi, iki ədəd itkin olarsa necə edərdiniz?

Daha əvvəl bu seçimi görməmişdim / eşitməmişdim və qəbul etməmişdim, buna görə panikalıyam və suala cavab verə bilmədim. Müsahib mənim düşüncə prosesini öyrənməkdə təkid etdi, buna görə də qeyd etdiyim kimi, biz gözlənilən məhsulla müqayisə edərək əlavə məlumat əldə edə bilərik və ya ilk pasdan bəzi məlumatlar yığdıqdan sonra ikinci dəfə keçə bilərik. Amma həqiqətən qaranlıq şəkilləri çəkdim və həqiqətən həll yolunda bir yol yoxdur.

Müsahib ikinci bir tənqidə malik olmağın həqiqətən problemin həll yollarından biri olduğunu söyləyərək məni təşviq etməyə çalışdı. Hal-hazırda qəzəbləndim (əvvəlki cavabı bilmədiyinə görə) və bu ümumi (proqramlaşdırılan) proqramlaşdırma texnikası olub-olmadığını soruşdu, ya da bu sualın yalnız bir oyun / cavab olsaydı.

Müsahibənin cavabı məni təəccübləndirdi: 3 əskik nömrəni tapmaq üçün texnika ümumiləşdirə bilərsiniz. Əslində, itkin nömrələri tapmaq üçün bunu ümumiləşdirə bilərsiniz.

Qk : Əgər cəmi kifayət qədər k ədəd olmadıqda, necə təsirli olardı?

Bir neçə ay əvvəl idi və mən hələ də hansı texnikanı başa düşmədim. Şübhəsiz ki, hər zaman ən azı bir dəfə bütün nömrələri Ω(N) olduğundan, vaxtın Ω(N) bir az sərhədi var, amma müsahibə TIME metodu və SPACE metodunun (minus O(N) tarama vaxtı) həllinin mürəkkəbliyinin K .

Beləliklə burada sual sadədir:

  • Q2-ə necə qərar verərdiniz?
  • Q3-ə necə qərar verərdiniz?
  • Qk-a necə qərar verərdiniz ?

Şərhlər

Yəni, yenidən giriş məlumatlarını O(N) -də taramalıyıq, ancaq kiçik bir məbləğdə informasiyanın yaza biləcəyini (k deyil, N nöqtəsi ilə müəyyənləşdirə bilərik), sonra da bir az k eksik nömrələrini tapmaq lazımdır.

1030
16 авг. polygen yağıraqlayıcılar 16 aug. 2010-08-16 13:26 '10 at 1:26 pm 2010-08-16 13:26
@ 47 cavab
  • 1
  • 2

Burada Dimitris Andreu ilə əlaqədar bir xülasə.

İ-ci qüvvələrin məbləğini xatırlayın, burada i = 1,2, .., k. Bu problemi tənliklər sistemini həll etmək üçün azaldır.

a 1 + a 2 + ... + a k = b 1

a 1 2 + a 2 2 + ... + a k 2 = b 2

...

a 1 k + a 2 k + ... + a k k = b k

Newton şəxsiyyətlərini istifadə edərək, b i hesablamaq üçün imkan verir

c 1 = a 1 + a 2 + ... a k

c 2 = a 1 a 2 + a 1 a 3 + ... + a k-1 a k

...

c k = a 1 a 2 ... a k

Əgər polinomu (xa 1 ) ... (xa k ) genişləndirsəniz, əmsallar tam olaraq c1 , ..., c k - Wiete formullarına baxın. Hər bir polinom faktoru unikal olduğundan (polinomların üzükləri bir Öklid domenidir ), yəni i birləşmənin dəyişməsinə qədər müəyyənləşdirilir.

Bu ədədləri bərpa etmək üçün bacarıqları yadda saxlamaq üçün kifayətdir. Sabit k üçün bu yaxşı bir yanaşma.

Lakin, k dəyişiklikləri, c 1 , ..., c k hesablamaq üçün birbaşa yanaşma olduqca bahalıdır, məsələn, ck bütün eksik nömrələrin məhsuludur, n! / (Nk) dəyəridir. Bunu aradan qaldırmaq üçün, q q z sahəsində q hesabları yerinə yetirmək üçün, burada q = n <= q <2n - Bertrandın postulatına görə mövcuddur. Düsturların hələ də yerinə yetirildiyi üçün sübutun dəyişdirilməsinə ehtiyac yoxdur və polinomların fərdiləşdirilməsi hələ də unikaldır. Həmçinin , BerlekampKantor-Zassenhaus alqoritmi kimi sonlu sahələrlə faktoring üçün bir alqoritm lazımdır.

Sabit k üçün yüksək səviyyəli pseudocode:

  • Verilən nömrələrin i-gücünü hesablayın
  • Bilinməyən nömrələrin i-ci gücünün cəmini almaq üçün çıxarın. B i olan məbləğlər hansılardır?
  • B i- dən əmsalları hesablamaq üçün Newton şəxsiyyətlərindən istifadə edin; onları c i çağırın. Əsasən c1 = b 1 ; c 2 = (c 1, b 1 - b 2 ) / 2; dəqiq formulalar üçün Vikipediya baxın
  • Polinom x k -c 1 x k-1 + ... + c k faktoru.
  • Polinomun kökləri lazımlı ədədlərdir. 1 , ..., k .

K dəyişmək üçün, məsələn, Miller-Rabin'i istifadə edərək, n <= q <2n sayını tapın və bütün ədədlərin modulo q azaldılması ilə addımları yerinə yetirin.

EDIT: bu cavabın bir əvvəlki versiyasında q qətfi deyil , q qətiyyən sadə, qəti xarakterik 2 (q = 2 ^ (log n)) sahəsini istifadə edə bilərsiniz. Nyuton formulalarının k qədər ədədlərə bölünməsini tələb etdiyi üçün belə deyil.

539
16 авг. Cavab sdcvvc 16 aug verilir . 2010-08-16 15:13 '10 at 15:13 2010-08-16 15:13

Muthukrishnan- bir neçə səhifəni oxuyaraq tapa bilərsiniz - məlumat axını alqoritmləri: puzzle 1: itkin nömrələri axtarın . Aradığınız dəqiq ümumiləşdirməni göstərir . Yəqin ki, müsahibinizin oxuduğu və niyə bu sualları soruşduqları.

İndi yalnız insanlar Muthukrishnan ilə müalicə əvəz və ya əvəz olan cavabları silmək və bu mətn daha asan tapmaq üçün başlaya bilər.

border=0

Həmçinin sdcvvc birbaşa əlaqəli cavabı da nəzərdən keçirin , bu da yalançı kodu (hurray! Bu kompleks riyazi formulları oxumağa ehtiyac yoxdur :)) (təşəkkür edirəm, böyük iş!).

231
16 авг. Dimitris Andreou tərəfindən verilmiş cavab 16 Avqust. 2010-08-16 14:26 '10 at 14:26 2010-08-16 14:26

Q2 nömrələrini özləri və ədədlərin meydanlarını yekunlaşdıraraq həll edə bilərik.

Sonra tapşırıqları azalta bilərik

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

xy : harada dəyərlər gözlənilən dəyərlərdən aşağıdır.

Əvəz bizi verir:

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

Daha sonra itkin ədədlərimizi təyin etməyə qərar verə bilərik.

166
Cavab anon verilir . 16 avqust 2010-08-16 13:37 '10 'da 13:37' da 2010-08-16 13:37

@ J_random_hacker qeyd etdiyimiz kimi, bu , O (n) vaxtında və O (1) yerində dublikatların tapılması və buraya cavabımı uyğunlaşdırmaq üçün də çox işlədir.

Çantanın ölçüsü A[] ölçüsü N - k k1 ilə təmsil olunduğuna görə, biz Q O(N) vaxtında və O(k) -də əlavə məsafədə həll edə bilərik.

Birincisi, arraylarımızı A[] ilə k elementləri ilə genişləndiririk, buna görə də indi N ölçüsü var. Bu əlavə yer O(k) . Sonra aşağıdakı pseudocode alqoritmini işləyirik:

 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 

Birinci loop, əlavə qeydləri k dizisində ilk rekord kimi eyni işə salır (bu, bildiyimiz kimi, artıq dizidə mövcuddur), bu addımdan sonra ilk Nk ölçüsündə itkin olan hər hansı qeydlər hələ də eksik geniş array).

İkinci loop geniş array ötürür, belə ki element x ən azı bir dəfə olsaydı, bu qeydlərdən biri A[x] mövqeyində olacaq.

Daxili bir döngə olsa da, o, hələ də O(N) vaxtında işləyir - mübadilə yalnız mövcud olduğunda meydana gəlir, belə ki A[i] != i və hər bir dəyişdirmə bu şəkildə ən azı bir element qoyur Əvvəllər bu həqiqət olmadığı A[i] == i idi. Bu, svopların ümumi sayını (və, əslində, while cəsədinin ümumi sayı) N-1 dən çox olmamaq deməkdir.

Üçüncü dövr i sətri ilə işğal olunmayan i serialının göstəricilərini yazır - bu mənim olmamam deməkdir.

128
22 апр. Cavab verilən kafedə 22 Aprel. 2011-04-22 07:32 '11 at 7:32 2011-04-22 07:32

Bu problemi həll etmək üçün 4 yaşlı bir uşaqdan soruşdum. O, nömrələri sıraladı və sonra saydı. Bu bir O (mətbəx mərtəbəsi) məkan tələb edir və bu, asanlıqla işləyir, lakin bir çox top eksik.

117
12 апр. Polkovnik Panik tərəfindən 12 apreldə cavab verildi 2013-04-12 21:59 '13 saat 09:59 'da 2013-04-12 21:59

Bu ən effektiv həll olduğuna əmin deyiləm, amma bütün qeydlərdən keçərdim və hansı ədəd verildiyini xatırlamaq üçün bit setindən istifadə edər və 0 bitin varlığını yoxlayıram.

Mən sadə həllər sevirəm - hətta hesab edirəm ki, bu, kvadratların cəmi və ya məbləğinin hesablanmasından və s.

32
16 авг. 16 Avqustda Chris Lercher tərəfindən verilmiş cavab 2010-08-16 13:38 '10 at 13:38 2010-08-16 13:38

Σ(n^2) yox etdim, amma hesab edirəm ki, Σ(n^2) hesablayarkən eyni səhv Σ(n^2) iki itkin ədədi almaq üçün kifayət qədər məlumat verəcəkdir, əgər Σ(n^3) üç və s. var

31
16 авг. AakashM 16 aug. 2010-08-16 13:38 '10 at 13:38 2010-08-16 13:38

Nömrələrin məbləğinə əsaslanan həllər problemi çox sayda nömrələri ilə saxlama və işləmənin dəyərini nəzərə almır ... praktikada çox böyük n üçün işləyir, çox sayda kitabxana istifadə ediləcəkdir. Bu alqoritmlər üçün yerin istifadəsini təhlil edə bilərik.

Sdcvvc və Dimitris Andreou alqoritmlərinin zaman və məkanının mürəkkəbliyini təhlil edə bilərik.

saxlama:

 l_j = ceil (log_2 (sum_{i=1}^ni^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}^ni)^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)` 

Beləliklə, l_j \in \Theta(j log n)

Ümumi \sum_{j=1}^k l_j \in \Theta(k^2 log n) yaddaş: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Istifadə olunan məkan: a^j hesablanması ceil(log_2 j) vaxt, ümumi vaxt:

 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^ni^i) + 1 t < kn log_2 (n) + 1 \in O(kn log n) 

Ümumi vaxt: \Theta(kn log n)

Bu vaxt və yer qənaətbəxşdirsə, sadə bir təkrarlayıcı alqoritmdən istifadə edə bilərsiniz. B olsun! Mən çanta içərisindəyəm, n silməkdən öncə nömrələrin sayı, k isə silinmə sayıdır. Haskell sözdizimində ...

 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..(nk)] 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 

O(k) istifadə edilən saxlama: O(k) bir yığın üçün bir siyahısı üçün O(log(n)) : O(k + log(n)) Bu alqoritm daha intuitivdir, eyni zamanda mürəkkəbliyə malikdir və daha az yer istifadə edir.

14
02 сент. cavab a1kmm 02 sep verilir . 2010-09-02 14:41 '10 at 2:41 PM 2010-09-02 14:41

Bir dəqiqə gözləyin. Bu suala cavab verildiyi kimi, çantada 100 ədəd var. Nə qədər böyük k olduğundan asılı olmayaraq, problem sabit bir zamanda həll edilə bilər, çünki bir setdən istifadə edə bilərsiniz və loopun 100 k-dən çox təkrarlaşdırılmasından bir sıra nömrələri silə bilərsiniz. 100 qalıcıdır. Qalan nömrələri yığmaq sizin cavabınızdır.

N ədədlərinin həllini 1-dən N-yə ümumiləşdirsək, heç bir şey dəyişmir, istisna olmaqla, N sabit deyildir, buna görə də biz (N-k) = O (N) zamanındayıq. Məsələn, bir bit dəsti istifadə edərsə, bitləri 1 (N) zamanında təyin edəcəyik, nöqtələr üzərində yineleyiz, hərəkət etdiyimizdə (O (Nk) = O (N)) bitləri təyin edin və sonra cavab veririk.

Mənə elə gəlir ki, müsahibə O (k) kateqoriyasında sonuncu məzmunun məzmununu O (N) deyil, necə çap etməyi xahiş etdi. Bir az dəst ilə nömrəni çap etdirməyin olub olmadığını müəyyən etmək üçün bütün N bitləri təkrarlamaq lazımdır. Bununla yanaşı, siz zənglərin həyata keçirilməsini necə dəyişdirdiyiniz təqdirdə, nömrələri k təkrarlama ilə yaza bilərsiniz. Bu, hash dəsti və ikili əlaqəli siyahıda saxlanılacaq bir obyektə ədəd qoymaqla həyata keçirilir. Bir obyekti bir xeyli dəstdən silməklə, onu da siyahıdan çıxarın. Artıq k uzunluğu olan siyahıda qalacaq cavablar qalır.

11
16 авг. JeremyP tərəfindən verilmiş cavab 16 avqust. 2010-08-16 14:25 '10 at 2:25 PM 2010-08-16 14:25

Burada hər hansı bir çətin fəndlər və sadə olmadan əlavə yaddaşın k bitlərini istifadə edən bir həlldir. O (n) icra müddəti, O (k) əlavə yer. Məhz bu qərarı ilk dəfə oxumasız və dahi olmamaqla həll edilə bilərik.

 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; } } } 
7
07 апр. Cavab verilir gnasher729 07 apr. 2014-04-07 21:53 '14 at 21:53 2014-04-07 21:53

2 (və 3) itkin nömrələri ilə bir problemi həll etmək üçün, orta hesabla O(n) quickselect dəyişdirə və quickselect yerinə quickselect sabit yaddaşdan istifadə edə bilərsiniz.

  • Təsadüfi çubuq p lərinə görə dəsti rotasiya oxundan daha az rəqəmləri olan bölm l lə bölün və rotasiya nöqtəsindən daha böyük rəqəmləri olan r bölün.

  • Hər bir hissənin ölçüsündə fırlanma dəyərini müqayisə etməklə 2 nömrəli ədədi tapın ( p - 1 - count(l) = count of missing numbers in ln - count(r) - p = count of missing numbers in r

  • a) Hər bir bölmədə vahid ədəd olmadıqda, hər bir itkin nömrəni axtarmaq üçün ümumi yanaşma fərqini istifadə edin.

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

    b) Bir bölmə yoxdur, hər iki nömrə və bölmə boşdur, onda itkin ədədlər (p-1,p-2) və ya (p+1,p+2) hansı bölmənin olmaması ilə bağlıdır.

    Bir hissədə iki ədəd yoxdur, ancaq boş deyilsə, bu hissəni yenidən başladın.

Yalnız iki itkin sayı ilə bu alqoritm həmişə ən azı bir bölmədən düşür, beləliklə, O(n) orta vaxt mürəkkəbliyini qısaldar. Eynilə, 3 ədəd itkin ədədi ilə bu alqoritm də hər keçişi ilə ən azı bir bölməni (iki itkin sayda olduğu kimi, maksimum 1 bölmədə bir neçə ədəd itkin ədəd ehtiva edir) keçir. Bununla yanaşı, daha çox itkin nömrələrin əlavə edilməsi ilə nə qədər məhsuldarlığın azaldılacağına əmin deyiləm.

Yerli bölməni istifadə etməyən bir tətbiqdir, beləliklə bu nümunə yerin tələblərinə cavab vermir, ancaq alqoritmanın addımlarını göstərir:

 <?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

6
08 нояб. Cavab FuzzyTree 08 noyabrda verilir. 2015-11-08 05:45 '15 saat 05:45 'da 2015-11-08 05:45

Hər bir nömrənin olub-olmadığını yoxlaya bilərsinizmi? Əgər belədirsə, aşağıdakıları edə bilərsiniz:

S = çanta olan bütün nömrələrin cəmi (S <5050)
Z = itkin nömrələrin sayı 5050 - S

əgər itkin ədədlər xy , onda:

x = Z - y və
max (x) = Z - 1

Beləliklə, aralığı 1 dən max(x) -ə qədər yoxlayın və nömrəni tapın

4
16 авг. cavab İlyan İlyev 16 avqustda verilir. 2010-08-16 13:37 '10 'da 13:37' da 2010-08-16 13:37

Bəlkə bu alqoritm 1 sual üçün işləyə bilər:

  1. İlk 100 tamsayılardan əvvəlcədən xora (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
  2. xor elementləri giriş axınından (val1 = val1 ^ next_input)
  3. son cavab = val ^ val1

Və ya daha yaxşı:

 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 

Bu alqoritm əslində iki ədəd itkin nömrəyə qədər uzadıla bilər. İlk addım eyni qalır. GetValue'yi iki ədəd itkin ədədlə çağırırıq, nəticədə a1^a2 - iki itkin ədəddir. Söyləyin

val = a1^a2

İndi val-dən a1 və a2-ni süzgəc etmək üçün val-dən hər hansı bir bit ala bilərik. ith bitinin val üçün təyin ith varsayalım. Bu, a1 və a2'nin ith bitinin mövqeyində fərqli bir paritetə ​​malik olduğunu bildirir. İndi biz qaynaq array üçün başqa bir iteration edirik və iki dəyər xorunu xilas edirik. Biri i-bitli setə sahib olan ədədlər üçün, ikincisi isə i-bit birləşməsinə malik olmayan digərlər üçün. İndi bizdə iki nömrə a1 and a2 biz a1 and a2 -nin müxtəlif seqmentlərdə yerləşəcəyini təmin edirik. İndi hər kovada bir itkin maddə tapmaq üçün etdiyimiz şeyi təkrarlayın.

4
06 дек. cavab bashrc 06 dekabrda verilir. 2011-12-06 15:03 '11 at 15:03 2011-12-06 15:03

Hər iki siyahının və hər iki siyahının məhsulu varsa, Q2-ə qərar verə bilərsiniz.

(l1 orijinal, l2 isə redaktə siyahısı)

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

Aritmetik seriyanın cəmi ilk dəfə və sonuncu üzvlərin ortalama dəyərindən n dəfə olduğundan, bunu optimallaşdıra bilərik:

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

İndi bilirik ki (əgər a və b silinmiş ədədlərdirsə):

 a + b = d a * b = m 

Beləliklə, biz yenidən qura bilərik:

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

Və çoxaltmaq:

 -b^2 + s*b = m 

Sağ tərəfin sıfır olması üçün yenidən qurun:

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

Sonra kvadrat formulu həll edə bilərik:

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

Nümunə Python 3 kodu:

 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 

Sqrt funksiyalarının, mürəkkəbləşmənin və məcmusunun mürəkkəbliyini bilmirəm, buna görə də bu həllin mürəkkəbliyini həll edə bilmirəm (əgər kiminsə bilirsə, aşağıda şərh edin).

3
16 нояб. 16 noyabr Tuomas Laakkonen tərəfindən verilmiş cavab 2014-11-16 19:14 '14 at 19:14 2014-11-16 19:14

Q2 üçün bu, digərləri ilə müqayisədə bir qədər az səmərəli olan bir həlldir, lakin O (N) icra vaxtına malikdir və O (k) yer tutur.

Fikir, iki dəfə orijinal alqoritmi çalıştırmaktır. В первом вы получаете общее количество, которое отсутствует, что дает вам верхнюю границу недостающих чисел. Позвольте называть это число N . Вы знаете, что недостающие два числа собираются суммировать до N , поэтому первое число может быть только в интервале [1, floor((N-1)/2)] , а второе - в [floor(N/2)+1,N-1] .

Таким образом, вы снова повторяете все числа, отбрасывая все числа, которые не включены в первый интервал. Те, которые есть, вы отслеживаете их сумму. Наконец, вы узнаете один из недостающих двух чисел, а второй - второй.

У меня такое ощущение, что этот метод может быть обобщен, и, возможно, несколько запросов выполняются "параллельно" в течение одного прохода над входом, но я еще не понял, как это сделать.

2
ответ дан Svalorzen 24 мая '16 в 19:51 2016-05-24 19:51

Вам, вероятно, нужно уточнить, что означает O (k).

Здесь тривиальное решение для произвольного k: для каждого v в вашем наборе чисел накапливается сумма 2 ^ v. В конце, цикл я от 1 до N. Если сумма поразрядно ANDed с 2 ^ я равна нулю, то я отсутствует. (Или численно, если пол суммы, деленной на 2 ^ i, является четным. Или sum modulo 2^(i+1)) < 2^i .)

Легко, правда? O (N) время, O (1) память, и это поддерживает произвольное k.

За исключением того, что вы вычисляете огромные числа, которые на реальном компьютере требуют пространства O (N). Фактически это решение идентично битовому вектору.

Таким образом, вы можете быть умным и вычислить сумму и сумму квадратов и сумму кубов... вплоть до суммы v ^ k, и сделать причудливую математику, чтобы извлечь результат. Но это тоже большие цифры, поэтому возникает вопрос: о какой абстрактной модели работы идет речь? Сколько места в O (1) пространстве, и сколько времени нужно, чтобы сложить числа любого размера вам нужно?

2
ответ дан sfink 10 авг. '16 в 0:52 2016-08-10 00:52

Существует общий способ обобщения таких алгоритмов потоковой передачи. Идея состоит в том, чтобы использовать немного рандомизации, чтобы надежно "распространить" элементы k на независимые вспомогательные проблемы, где наш исходный алгоритм решает проблему для нас. Между прочим, этот метод используется, в частности, при редовом восстановлении сигнала.

  • Сделайте массив a размером u = k^2 .
  • Выберите любую , h : {1,...,n} -> {1,...,u} . (Как multiply-shift )
  • Для каждого i в 1, ..., n увеличение a[h(i)] += i
  • Для каждого номера x во входном потоке декремент a[h(x)] -= x .

Если все недостающие числа были хэшированы в разные ковши, ненулевые элементы массива теперь будут содержать недостающие числа.

Вероятность того, что конкретная пара отправляется в одно и то же ведро, меньше, чем 1/u по определению универсальной хэш-функции. Поскольку существует пара k^2/2 , мы имеем, что вероятность ошибки не превосходит k^2/2/u=1/2 . То есть с вероятностью мы получим минимум 50%, и если мы увеличим u , мы увеличим наши шансы.

Обратите внимание, что этот алгоритм принимает k^2 logn бит пространства (нам нужны бит logn для каждого массива). Это соответствует пространству, требуемому ответом @Dimitris Andreou (в частности, требование пространства полиномиальной факторизации, которое также происходит быть рандомизированным.) Этот алгоритм также имеет постоянное время на обновление, а не время k в случае энергетических сумм.

На самом деле мы можем быть даже более эффективными, чем метод суммирования мощности, используя трюк, описанный в комментариях.

2
ответ дан Thomas Ahle 26 апр. '16 в 0:54 2016-04-26 00:54

Я думаю, что это можно сделать без каких-либо сложных математических уравнений и теорий. Ниже представлено предложение о решении проблемы времени и O (2n):

Предположения входной формы:

# чисел в сумке = n

# недостающих чисел = k

Числа в сумке представлены массивом длины n

Длина входного массива для algo = n

Отсутствующие записи в массиве (числа, выведенные из мешка) заменяются значением первого элемента массива.

Məsələn, Первоначально сумка выглядит как [2,9,3,7,8,6,4,5,1,10]. Если вынуть 4, значение 4 станет 2 (первый элемент массива). Поэтому после взятия 4 из мешка будет выглядеть как [2,9,3,7,8,6,2,5,1,10]

Ключом к этому решению является пометка INDEX посещаемого числа путем отрицания значения в этом INDEX по мере прохождения массива.

  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; } 
2
ответ дан pickhunter 12 дек. '12 в 21:57 2012-12-12 21:57

Вы можете мотивировать решение, думая об этом в терминах симметрии (группы, в математическом языке). Независимо от порядка набора чисел, ответ должен быть таким же. Если вы собираетесь использовать функции k , чтобы помочь определить недостающие элементы, вы должны думать о том, какие функции имеют это свойство: симметричное. Функция s_1(x) = x_1 + x_2 + ... + x_n является примером симметричной функции, но есть и другие более высокой степени. В частности, рассмотрим элементарные симметричные функции . Элементарная симметричная функция степени 2 равна s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n , сумме всех произведений двух элементов. Аналогично для элементарных симметричных функций степени 3 и выше. Они, очевидно, симметричны. Кроме того, оказывается, что они являются строительными блоками для всех симметричных функций.

Вы можете построить элементарные симметричные функции, указав это s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)) . Дальнейшая мысль должна убедить вас, что s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1)) и т.д., Поэтому их можно вычислить за один проход.

Как мы узнаем, какие элементы отсутствовали в массиве? Подумайте о многочлене (z-x_1)(z-x_2)...(z-x_n) . Он оценивает значение 0 , если вы введете любое из чисел x_i . Развернув многочлен, вы получите z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n . Здесь также появляются элементарные симметричные функции, что неудивительно, так как многочлен должен оставаться неизменным, если мы применяем любую перестановку к корням.

Итак, мы можем построить многочлен и попытаться определить его, чтобы выяснить, какие числа не находятся в наборе, как упомянули другие.

Наконец, если мы обеспокоены переполнением памяти большими числами (n-й симметричный многочлен будет иметь порядок 100! ), мы можем сделать эти вычисления mod p , где p является просто большим, чем 100. В в этом случае мы вычисляем многочлен mod p и обнаруживаем, что он снова оценивает 0 , когда ввод представляет собой число в наборе, и он вычисляет ненулевое значение, когда ввод является числом, не входящим в набор. Однако, как указывали другие, чтобы получить значения из полинома во времени, зависящие от k , а не N , мы должны разложить многочлен mod p .

1
ответ дан Edward Doolittle 21 апр. '15 в 7:57 2015-04-21 07:57

Еще одним способом является использование остаточной фильтрации графов.

Предположим, у нас есть номера от 1 до 4, а 3 отсутствует. Бинарное представление следующее,

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

И я могу создать потоковую диаграмму, как показано ниже.

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

Обратите внимание, что потоковый граф содержит х узлов, а х - количество битов. И максимальное количество ребер (2 * x) -2.

Таким образом, для 32-разрядного целого числа потребуется O (32) пробел или O (1) пробел.

Теперь, если я уберу емкость для каждого числа, начиная с 1,2,4, то у меня останется остаточный график.

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

Наконец, я запустите цикл, как показано ниже,

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

Теперь результат в result содержит числа, которые также не пропущены (ложное срабатывание). Но k <= (размер результата) <= n, когда есть k пропущенных элементов.

Я пройду по списку в последний раз, чтобы отметить, что результат отсутствует или нет.

Таким образом, сложность времени будет O (n).

Наконец, можно уменьшить количество ложных срабатываний (и необходимое пространство), взяв узлы 00 , 01 , 11 , 10 вместо просто 0 и 1 .

1
ответ дан shuva 20 июля '18 в 18:55 2018-07-20 18:55

Я бы взял другой подход к этому вопросу и исследовал интервьюера для получения более подробной информации о более крупной проблеме, которую он пытался решить. В зависимости от проблемы и требований, связанных с ней, очевидное решение на основе набора может быть правильным, а метод generate-a-list-and-pick-through-it-afterward не может быть.

Например, может случиться так, что интервьюер отправит сообщения n и должен знать k , который не привел к ответу, и должен знать его как можно меньше настенных часов после приходит ответ nk th. Предположим также, что природа канала сообщений такова, что даже работает на полном расстоянии, достаточно времени для выполнения некоторой обработки между сообщениями, не оказывая никакого влияния на то, сколько времени потребуется, чтобы получить конечный результат после последнего ответа. Это время можно использовать для вставки некоторого идентифицирующего аспекта каждого отправленного сообщения в набор и удаления его по мере поступления каждого соответствующего ответа. Как только последний ответ пришел, единственное, что нужно сделать, это удалить его идентификатор из набора, который в типичных реализациях принимает O(log k+1) . После этого набор содержит список k отсутствующих элементов и дополнительной обработки не требуется.

Это, конечно, не самый быстрый подход для пакетной обработки предварительно сгенерированных пакетов чисел, потому что все это работает O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)) . Но он работает для любого значения k (даже если оно не известно заранее), а в приведенном выше примере оно применялось таким образом, чтобы минимизировать самый критический интервал.

1
ответ дан Blrfl 03 сент. '10 в 5:57 2010-09-03 05:57

Очень хорошая проблема. Я бы воспользовался набором разностей для Qk. Многие языки программирования даже поддерживают его, как в Ruby:

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

Это, вероятно, не самое эффективное решение, но оно будет использоваться в реальной жизни, если бы я столкнулся с такой задачей в этом случае (известные границы, низкие границы). Если бы набор чисел был бы очень большим, я бы рассмотрел более эффективный алгоритм, конечно, но до тех пор для меня было бы достаточно простого решения.

1
ответ дан DarkDust 16 авг. '10 в 14:18 2010-08-16 14:18

Я думаю, что это можно обобщить следующим образом:

Обозначим S, M как начальные значения суммы арифметических рядов и умножения.

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

Я должен подумать о формуле для вычисления этого, но это не главное. В любом случае, если один номер отсутствует, вы уже предоставили решение. Однако, если отсутствуют два числа, то обозначим новую сумму и суммарное кратное через S1 и M1, что будет следующим:

 S1 = S - (a + b)....................(1) Where a and b are the missing numbers. M1 = M - (a * b)....................(2) 

Поскольку вы знаете S1, M1, M и S, приведенное выше уравнение разрешимо для нахождения a и b, недостающих чисел.

Теперь для трех отсутствующих чисел:

 S2 = S - ( a + b + c)....................(1) Where a and b are the missing numbers. M2 = M - (a * b * c)....................(2) 

Теперь ваше неизвестное - 3, в то время как у вас есть только два уравнения, из которых вы можете решить.

0
ответ дан Jack_of_All_Trades 16 авг. '13 в 17:26 2013-08-16 17:26

Я не знаю, является ли это эффективным или нет, но я хотел бы предложить это решение.

  • Вычислить xor из 100 элементов
  • Вычислить xor из 98 элементов (после удаления двух элементов)
  • Теперь (результат 1) XOR (результат 2) дает вам xor двух отсутствующих nos i..e XOR b, если a и b являются отсутствующими элементами
    4. Получите сумму отсутствующих Nos с вашим обычным подходом формулы diff diff и скажем, что diff - d.

Теперь запустите цикл, чтобы получить возможные пары (p, q), оба из которых лежат в [1, 100] и суммируются с d.

Когда получается пара, проверьте (результат 3) XOR p = q и если да, то мы закончили.

Пожалуйста, поправьте меня, если я ошибаюсь, а также прокомментируйте временную сложность, если это правильно.

0
ответ дан user2221214 05 авг. '14 в 0:49 2014-08-05 00:49

Я считаю, что есть пробел времени O(k) и O(log(k)) , если у вас есть функции floor(x) и log2(x) для произвольно больших целых чисел:

У вас есть k -битное длинное целое число (следовательно, log8(k) ), где вы добавляете x^2 , где x - следующее число, которое вы найдете в сумке: s=1^2+2^2+... Это занимает время O(N) (что не является проблемой для интервьюера). В конце вы получите j=floor(log2(s)) , который является самым большим числом, которое вы ищете. Затем s=sj , и вы снова сделаете следующее:

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

Теперь у вас обычно нет функций floor и log2 для целых чисел 2756 -bit, но вместо этого для парных. Так? Просто для каждого 2 байта (или 1, или 3 или 4) вы можете использовать эти функции для получения желаемых номеров, но это добавляет фактор O(N) к временной сложности

0
ответ дан CostasGR43 07 сент. '10 в 17:43 2010-09-07 17:43
 $removedNumbers = array_flip(range(50, 200)); foreach($secretNumberBagRange_50_200 as $value) { unset($removedNumbers[$value]); } 
0
ответ дан Christoffer Bubach 19 дек. '18 в 2:31 2018-12-19 02:31

Мы можем делать Q1 и Q2 в O (log n) большую часть времени.

Предположим, что наш memory chip состоит из массива n числа test tubes . И число x в пробирке представлено x milliliter химической жидкости.

Предположим, что наш процессор является laser light . Когда мы зажигаем лазер, он пересекает все трубки перпендикулярно длине. Каждый раз, когда он проходит через химическую жидкость, светимость уменьшается на 1 . И прохождение света на определенной отметке миллиметра - это операция O(1) .

Теперь, если мы зажжем наш лазер в середине пробирки и получим светимость

  • равно предварительно рассчитанному значению (вычисленному, когда номера отсутствовали), то недостающие числа больше, чем n/2 .
  • Если наш результат меньше, то есть хотя бы одно недостающее число, которое меньше n/2 . Мы также можем проверить, уменьшена ли яркость на 1 или 2 . если оно уменьшено на 1 , то одно отсутствующее число меньше, чем n/2 , а другое больше, чем n/2 . Если оно уменьшено на 2 , то оба числа меньше n/2 .

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

Параллельные алгоритмы, которые стоит упомянуть (потому что они интересны),

  • сортировка по некоторому параллельному алгоритму, например, параллельное слияние можно выполнить в O(log^3 n) времени. И тогда недостающее число может быть найдено двоичным поиском в O(log n) времени.
  • Теоретически, если у нас есть процессоры n , то каждый процесс может проверять один из входов и устанавливать некоторый флаг, который идентифицирует число (удобно в массиве). И на следующем шаге каждый процесс может проверять каждый флаг и, наконец, выводить число, которое не помечено. Весь процесс займет время O(1) . Он имеет дополнительное требование O(n) пространства/памяти.

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

0
ответ дан shuva 11 дек. '17 в 22:25 2017-12-11 22:25

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

Итак, поскольку вы видите все цифры, просто найдите номер, который отсутствует. То же самое происходит, когда отсутствуют два числа. Довольно просто, я думаю. Нет смысла использовать уравнение, когда вы увидите цифры, оставшиеся в сумке.

0
ответ дан Stephan M 02 сент. '10 в 6:27 2010-09-02 06:27

Вы можете попробовать использовать Bloom Filter . Вставьте каждое число в сумке в цвету, а затем перейдите по полному набору 1-k, пока не сообщите, что каждый из них не найден. Это может не найти ответ во всех сценариях, но может быть достаточно хорошим решением.

0
ответ дан jdizzle 02 сент. '10 в 19:29 2010-09-02 19:29

в одном случае это должно было бы вычислять по модулю простое число 101.

вычислить и сохранить произведение целых чисел 1 до 100, уменьшить это число по модулю 101. Маленький exo: результат будет равен 1.

вычислить и сохранить сумму всех чисел 1 до 100, уменьшить результат по модулю 101. Маленький exo: результат будет 0.

теперь предположим, что сумка имеет числа x и y удалены.

Рассчитайте произведение и сумму всего в сумке по модулю 101. Поэтому я буду знать значения

a = x + y и b = x * y

по модулю 101.

теперь легко найти x и y по модулю 101 (решаем квадратичные поли над конечным полем с 101 элементом).

Теперь вы знаете x и y по модулю 101. но так как вы также знаете, что x и y меньше 101, вы знаете их истинные значения.

-1
ответ дан mnr 29 дек. '17 в 13:20 2016-12-29 13:20
  • 1
  • 2

Другие вопросы по меткам или Задайте вопрос