5
Podano tablicę n liczb, gdzie n jest liczbą parzystą. Należy określić maksymalną i minimalną liczbę n. Muszę znać potrzebne porównania?Maksymalne i minimalne wartości tablicy
A
Odpowiedz
3
Można to zrobić w czasie O (n).
Możesz sprawdzić ten link odsyłające
+0
Żartujesz, prawda? Używając naiwnego podejścia, można to zrobić w O (N) –
+0
@IvayloStrandjev: - Popraw mnie, jeśli się mylę, ale uznałem to za tablicę 2D. Czy jest to możliwe również w macierzy 2D, czyli O (n) czasie? –
+0
'Tablica liczb n jest podana, gdzie n jest liczbą parzystą. Należy określić maksymalną i minimalną liczbę n. Nie widzę tu żadnej wzmianki o 2D. OP prosi o znalezienie minimalnej i maksymalnej liczby spośród n liczb przy minimalnej liczbie porównań. –
4
Można to zrobić za pomocą 3*n/2-2 porównań.
Dla n == 2 wystarczy porównać dwie liczby. Załóżmy teraz, że mamy minimum i maksimum dla pierwszych numerów n-2. Porównaj pozostałe dwie liczby, a następnie porównaj większą z poprzednią maksymalną, a mniejszą z poprzednią.
1
Dla nieposortowanych tablic można to zrobić w przybliżeniu w przybliżeniu 1.5n. Możesz to zrobić, porównując pary elementów tablicy i przechowując min i lokalną max. Zrobiłeś n/2 porównań, aby znaleźć (miejscowi) max i n/2, aby znaleźć min. W sumie w tej fazie jest n.
Teraz przechodzisz przez miejscowych max i min i znajdujesz globalne maksimum i min. Wymagałoby to również porównań n/2. Tak więc n + n/2 = 1.5n.
Jeśli tablica jest posortowana można go znaleźć bez żadnych porównań, ponieważ najniższy numer jest na pozycji 0, a najwyższy na pozycji N - 1.
Powiązane problemy
- 1. Minimalne i maksymalne wartości Java w tablicy
- 2. Python: użyteczne wartości maksymalne i minimalne:
- 3. Znajdź wartości minimalne i maksymalne funkcji
- 4. gnuplot: wartości maksymalne i minimalne w zakresie
- 5. podkreślić, aby znaleźć minimalne i maksymalne wartości obiektu
- 6. jQPlot wymusza statyczne wartości minimalne i maksymalne na osi Y
- 7. Jak mogę uzyskać maksymalne i minimalne wartości w jednym zapytaniu?
- 8. Maksymalne i minimalne rozmiary okien w WINAPI
- 9. NumPy minimalne/maksymalne przypisanie na miejscu
- 10. znajdź unikalne minimalne i maksymalne daty z 4 tabel - php
- 11. Jak utworzyć tabelę przedstawiającą wartości minimalne i maksymalne ze wszystkich kolumn podanych w tabeli?
- 12. Powłoka uniksowa ustalająca wartości maksymalne i minimalne oraz drukowanie linii z pliku
- 13. Jak ustawić minimalne i maksymalne rozmiary rozmiaru dla mojego głównego okna?
- 14. D3.js - Jak wyróżnić największe i najmniejsze (minimalne i maksymalne) kolumny na wykresie słupkowym?
- 15. Jak uzyskać minimalne i maksymalne ustawienia wielkości sterty JVM z poziomu programu Java?
- 16. 5 maksymalne wartości w słowniku Pythona
- 17. NSDate Min i Max Możliwe wartości
- 18. Znajdź minimalne wartości w python 3.3 liście
- 19. Znajdź minimalne wartości spośród 5 liczb całkowitych?
- 20. znajdź wszystkie minimalne elementy dwuwymiarowej tablicy w Matlab
- 21. numeric_limits najniższe i minimalne funkcje składowe
- 22. Ograniczać minimalne/maksymalne powiększenie mapy Bing za pomocą v7 kontrolki AJAX?
- 23. Obliczyć maksymalne wiersze
- 24. Maksymalne kolumny konsoli w C#
- 25. Extract wszystkie wartości maksymalne długości w postaci wektorowej w R
- 26. Edytor Kendo UI max i minimalne znaki
- 27. Jak uzyskać typy i wartości tablicy const?
- 28. jquery wcisnąć klawisz i wartości w tablicy
- 29. Sortowanie tablicy i zachować wartości kluczy
- 30. Konwersja właściwości i wartości obiektu do tablicy par wartości klucza
Podpowiedź: 3 * n/2-2 porównania są wystarczająco . – Henrik
@ Henrik, proszę, rozwiąż zagadkę – user2170497