m liczb całkowitych brakujących w tablicy o rozmiarze n

To interesujące pytanie, które napotkałem jakiś czas temu i miałem problemy z jego rozwiązaniem.m liczb całkowitych brakujących w tablicy o rozmiarze n

Jest takie sortowania tablicy całkowitą wielkość N przechowywane numerami 1,2 .., n + m z M całkowite brakuje go. M i N są znane wcześniej. Napisz algorytm, aby znaleźć brakujące liczby całkowite w najbardziej efektywny sposób.

próbowali przyporządkowując je do macierzy o rozmiarze N + M, tak że i tym indeksie zawiera element o wartości I, ale wymaga to 2 skany (1 dla mapowaniu 1 dla znalezienia brakujących numerów M).

Książka, w której natknąłem się na ten wzmiankę o pojedynczym rozwiązaniu skanowania, jest możliwa, ale nie mogłem do niego dotrzeć. Wszelkie pomysły, jak to zrobić?

Źródło

2012-11-09 sanz

Mógłbyś zapisać jeden skan algo? Dzięki. –

To pytanie wydaje się być bardzo zlokalizowane i nie dostarczyłeś żadnych dowodów na to, że sam próbowałeś rozwiązać problem. – lockstock

@ Lockstock przepraszam za to. Zmieniłem to pytanie. Mam nadzieję że to pomoże. – sanz

Możesz to zrobić z podwójnie połączoną listą zmapowaną na szczycie tablicy.

position 1 2 3 4 5 6 ... 
next  2 3 4 5 6 7 ... 
prev  0 1 2 3 4 5 ...

Na przejściu przez wejście Ci indeks do pozycji odpowiadającej każdej liczby wejściowego i aktualizuje połączonej listy usunąć (pominąć) to stanowisko z połączonej listy. Po zakończeniu wprowadzania lista połączona będzie zawierać tylko pozycje, które nie zostały odwiedzone.

Źródło

2012-11-09 03:40:11

Ale czy nie musisz przeglądać listy połączonej, aby wydrukować brakujące liczby całkowite? To pętla '> 1', jak rozumiem? – irrelephant

@irrelephant Założę się, zakładając, że chcesz je wydrukować. Nie wydaje mi się, żebyś mógł lepiej z punktu widzenia złożoności czasu, że "O (N) + O (M)", ponieważ dopóki nie osiągniesz końca "N", nie możesz znać ostatniego z braków z 'M ' '. Jeśli już zaczynałeś drukowanie, ostatni z 'N' może zepsuć twoje wyniki, zawierając coś, co już wydrukowałeś. Jestem pewien, że prawdopodobnie można zrobić lepiej z perspektywy złożoności przestrzeni, gdy M << N, jako [raczej imponująco wyglądająca odpowiedź matematyczna] (http://stackoverflow.com/a/3492967/1756702) jest połączona z komentarzem powyżej wydaje się robić. –

Nie powinienem był używać tam zapisu Big-O. Chciałem powiedzieć, że nie sądzę, że nie można zrobić nic lepszego niż pojedyncze przejście przez 'N' i' M', jeśli chcesz wydrukować 'M'. –

m liczb całkowitych brakujących w tablicy o rozmiarze n

Odpowiedz

Powiązane problemy