Witam, mam problem z taką listą:
List<int> list = new List<int> { 10, 30, 90, 30, 100, 20, 10, 0, 30, 40, 40, 70, 70 };
Jak wypisać trzy największe wartości z tej listy?
C# 
- Rejestracja:około 5 lat
- Ostatnio:23 minuty
- Postów:109
2
1 link z google
https://lmgtfy.app/?q=how+to+get+first+n+element+from+list+C%23
- Rejestracja:około 8 lat
- Ostatnio:2 minuty
- Postów:4884
1
nie wiem jak się za to zabrać i jaką metodą to zrobić a szukałem już dużo w dokumentacji
To chyba proste, znaleźć maksimum, odłożyć na bok, znowu szukać maksimum, tylko teraz ignorować to wcześniejsze i jeszcze raz to samo, tylko ignorować oba poprzednie.
- Rejestracja:prawie 6 lat
- Ostatnio:prawie 4 lata
- Lokalizacja:Warszawa
- Postów:2918
1
stivens napisał(a):
Dolna granica dla tego problemu to n ale nlogn raczej Cie nie boli :)
Problem jest O(n)
buildMaxHeap to O(n)
takeMax from heap to O(1)
O(n) + 3 * O(1) = O(n)
PS
Wiem, dla OPa to nie pomoc, ale gdyby ktoś próbował rekrutacji z Codility itp to warto wiedzieć co to Heap, co to heapify, jak się buduje heap i dlaczego to O(n).
Ostatnio Codility i podobne algorytmiki są co raz częściej spotykane
edytowany 1x, ostatnio: BraVolt
Mech codishityly a w zyciu realnym kazdy zrobi sort wbudwoana funkcja....
- Rejestracja:ponad 8 lat
- Ostatnio:około 3 godziny
0
Zdjecie (usuniecie) elementu z kopca jest O(logn) ;)
A potrzebujesz 3 elementy a nie jeden.
Edit: chociaz w sumie to jest O(n) + O(3logn) wiec O(n).
Ale na prawde nie sadze zeby dla OPa to mialo znaczenie... Ergo niepotrzebnie w ogole o tym gadamy.
edytowany 5x, ostatnio: stivens
Zobacz pozostałe 22 komentarze
@stivens: narysowałem sobie 'problem' według poradników 'faang interviews', arr[0] to max, vice-max to większa liczba z pary arr[1], arr[2]. To jest max heap, left child i right child to też max heaps. Każda z nich ma swój max, wybieramy ten większy. Dla 3 największych trzeba porównać jeszcze dzieci (wnuki) - z 6 wartości wybrać 2 największe. Nic nie trzeba usuwać, bo cała struktura jest 100% heap, robimy tylko odczytanie informacji z max, 2 dzieci i 4 wnuków. Całość to O(n) bo musimy tylko zbudować heap, a na samej górze 2 poziomy w miarę prosto przeskanujemy szukając max
Nie trzeba usuwać max, można wziąć odczytać większy z jego dzieci i będzie drugi co do max wielkości.
Nawet z usuwaniem jest O(n)
Jak usuwasz, w domyśle dużo usuwasz, to robi się HeapSort O(n). IMHO 2 max elementy przejdzie (łatwo się czyta bez usuwania), 4, 5 (szukanie wielu sub-heap albo usuwanie) to już naciągane, bo nawet od miliarda logarytm to 30. Coś w rodzaju 100n i n*log(n), gdzie nlog(n) wygrywa w praktyce z O(n). log(n) to jest taki niszczyciel światów danych. Była galaktyka miliarda gwiazd, Darth Vader strzela z logarytmu, zostało 30. Po co się rozdrabniać i szukać rebeliantów jedna planeta po drugiej? :)
- Rejestracja:ponad 7 lat
- Ostatnio:4 miesiące
- Lokalizacja:Śląsk
- Postów:46
0
@lion137:Dzięki za pomoc!, zrobiłem to twoim sposobem:
public List<int> PersonalTopThree()
{
List<int> list = new List<int> { 10, 30, 90, 30, 100, 20, 10, 0, 30, 40, 40, 70, 70 };
List<int> lista = new List<int>();
list.Sort();
for (int i = 0; i < 3; i++)
{
lista.Add(list.Max());
list.Remove(list.Max());
}
return lista;
Ogólnie to sprawa wygląda tak, że robię zadanka na praktyki (jestem na kierunku technik informatyk 3 rok, więc moje umiejętności nie są zbyt duże :p) i muszę napisać program tak aby przeszedł testy jednostkowe. Więc udał się pierwszy test z pięciu które wkleję poniżej (wcześniej było jeszcze kilka ale z nimi sobie poradziłem). Pytanie jak zrobić cztery następne testy? Będzie to trochę bardziej złożone. Oczywiście pokminie to sam, ale będe bardzo wdzięczny jak dacie mi jakieś wskazówki :)
[Fact]
public void Personal_top_three_from_a_list_of_scores()
{
var sut = new HighScores(new List<int> { 10, 30, 90, 30, 100, 20, 10, 0, 30, 40, 40, 70, 70 });
Assert.Equal(new List<int> { 100, 90, 70 }, sut.PersonalTopThree());
}
[Fact(Skip = "Remove this Skip property to run this test")]
public void Personal_top_highest_to_lowest()
{
var sut = new HighScores(new List<int> { 20, 10, 30 });
Assert.Equal(new List<int> { 30, 20, 10 }, sut.PersonalTopThree());
}
[Fact(Skip = "Remove this Skip property to run this test")]
public void Personal_top_when_there_is_a_tie()
{
var sut = new HighScores(new List<int> { 40, 20, 40, 30 });
Assert.Equal(new List<int> { 40, 40, 30 }, sut.PersonalTopThree());
}
[Fact(Skip = "Remove this Skip property to run this test")]
public void Personal_top_when_there_are_less_than_3()
{
var sut = new HighScores(new List<int> { 30, 70 });
Assert.Equal(new List<int> { 70, 30 }, sut.PersonalTopThree());
}
[Fact(Skip = "Remove this Skip property to run this test")]
public void Personal_top_when_there_is_only_one()
{
var sut = new HighScores(new List<int> { 40 });
Assert.Equal(new List<int> { 40 }, sut.PersonalTopThree());
}
- Rejestracja:ponad 22 lata
- Ostatnio:7 dni
- Rejestracja:ponad 4 lata
- Ostatnio:ponad 2 lata
- Lokalizacja:Poznań
- Postów:20
0
List<int> list = new List<int> { 10, 30, 90, 30, 100, 20, 10, 0, 30, 40, 40, 70, 70 };
var listaWynikow = Sortowanie(list, 3);
List<int> Sortowanie(List<int> lista, int ilosc)
{
var result = new int[ilosc];
Array.Copy(lista.OrderByDescending(x => x).ToArray(), result, result.Length);
return result.ToList();
}
