Biorąc N dowolne liczby całkowite, jak znaleźć średnią z górnej połowy tych liczb? Czy istnieje rozwiązanie O (n)? Jeśli nie, to można udowodnić, że nie jest to możliwe?Jak znaleźć średnią najwyższą połowę N liczb?
Najpierw znajdź median danej tablicy (to takes linear time).
Następnie wystarczy przejść przez tablicę i zsumować wszystkie elementy, które są większe od mediany.
Policz ile elementów zostało zsumowanych (M). Jeśli jest to M < N/2, oznacza to, że kilka elementów, które są równe wartości medianowej (mianowicie N/2 - M), należy do górnej połowy. Dodaj do swojej sumy tyle wartości median. Potrzebujemy tej złożoności, ponieważ nie wiemy, ile elementów mediany (może być ich kilka) należy do najwyższej półki: jeśli weźmiemy je wszystkie, możemy w końcu zsumować więcej niż N/2 elementów.
Teraz masz sumę górnej połowy tablicy. Podziel przez N/2 i gotowe.
Lub kod może być prostszy, jeśli wykonasz dodatkowe O (n) podanie i po prostu policz liczbę elementów równą medianie. To mówi ci, ile równych do median elementów należy uwzględnić w średniej. –
Jeszcze prostsze byłoby użycie tego, że prawie każdy algorytm znajdowania mediany znajduje również partycję listy wejściowej w górnej i dolnej połowie. Stąd po znalezieniu mediany wszystkie elementy w górnej połowie są już znane. – Accipitridae
Proponuję tak:
Zastosowanie Quicksort wybierz jakąś pivot. Spowoduje to podzielenie listy na dwie podlisty, jedną mniejszą niż oś obrotu, o jedną większą. Jeśli rozmiar mniejszej podlisty to < = N/2, obliczyć średnią, powiedz: a1.
Jeśli zostanie wykonana natychmiast.
W przypadku braku ponownej partycji większa podlista do całkowitego rozmiaru wynosi N/2.
Jeśli rozmiar> N/2 dzieli mniejszą podlistę.
Powtórz wszystkie czynności do zrobienia.
P.S: Nie trzeba sortować.
To jest "O (n^2)" w najgorszym przypadku ... –
Możesz użyć kolejki priorytetowej. Wstaw elementy do kolejki, utrzymując liczbę wyświetlanych elementów, n. Wyodrębnij maksimum elementów z kolejki do akumulatora i obliczyć średnią.
Dzięki dobrze wybranej strukturze danych za kolejką, takiej jak stertę Fibonacciego, pojawi się O(n log n) runtime, ponieważ wstawienie to O(1), a wyodrębnienie to O(log n).
Niestety, nie dotyczyło to środowiska wykonawczego O (n), ale w przypadku już zaimplementowanej struktury danych generowałoby to bardzo zrozumiały kod.
* Odnalezienie * maksimum to O (1) w sterty Fibonacciego, ale * usunięcie * to (co pozwoliło na to, co było sekundą do można znaleźć w innym O (1)) to O (log n). Jeśli "insert" i "remove max" rzeczywiście byłyby O (1) w stertach Fibonacciego, to byłoby możliwe użycie jednego do sortowania porównawczego w O (n). –
Masz całkowitą rację, przepraszam, odpowiednio zredagowałem swoją odpowiedź. To brzydkie nlogn niższa granica przy sortowaniu! –
Jest to oczywiście rozwiązalne w czasie liniowym, jeśli można znaleźć medianę w czasie liniowym. A znalezienie mediany w czasie liniowym jest trudne, ale możliwe. Zobacz na przykład artykuł wikipedia na selection algorithms.
Czy pytanie ma odnosić się do programowania (tj. Rozwiązać to za pomocą programu)? – BoltClock
I donno. Możesz podać wzór matematyczny, jeśli masz metodę. To tylko pytanie do wywiadu. – Seeker
Jest to jedno z pytań, na które osoba przeprowadzająca wywiad chce wiedzieć, czy kandydat może zredukować problemy związane ze światem rzeczywistym do znanych algorytmów. Jest to często ważniejsze niż możliwość recytowania samych algorytmów. Dlatego trudno mi zrozumieć, dlaczego to pytanie zostało zamknięte jako nie na temat. – Accipitridae