Sıralayınca cevap belli bir yere düşer

Bir değer listenin yarısından fazlasını kaplıyorsa, liste sıralandığında tam ortadaki eleman mutlaka odur: yarıdan uzun bir blok, nereye yerleşirse yerleşsin ortayı kapsar. Bazı sorular sıraladıktan sonra tek bir indekse bakmaya iner.

1ordered = sorted(scores, reverse=True)
2rank = 0
3while rank < len(ordered) and ordered[rank] > rank:
4    rank += 1
5return rank

Büyükten küçüğe sıralayıp "kaçıncı sıradayım" ile "değerim kaç" sorularını karşılaştırmak: değeri sırasından büyük olan elemanları sayar. H-indeks gibi "en az h tanesi en az h" biçimindeki tanımlar böyle okunur.

Sıralamak her zaman en hızlı yol değildir ama neredeyse her zaman en kolay doğru yoldur. Önce sıralayarak çöz ve geçtiğini gör; sonra "sıralamadan, tek geçişte yapabilir miyim?" diye sor. Çoğunluk elemanı için cevap evettir: bir aday ve bir sayaç yeter.

Görevler