return -1;
}
==

Această soluţie are complexitatea O(n log n), nu foloseşte suplimentară, dar suprascrie şirul iniţial.
O idee ce ne vine pe urma acestei rezolvări este aceea că în şirul sortat, un element majoritar se va afla în şirul sortat şi pe poziţia n/2.Ştim că există algoritmi de selecţie care ne găsesc elemente de poziţie o fixată k din şirul sortat în complexitate O(n). Astfel vom găsi mai întâi elementul de pe poziţia n/2 iar apoi vom verifica dacă acesta este elementul majoritar al şirului. Astfel avem o soluţie de complexitate O(n) iar şirul iniţial va fi modificat. Există metode de selecţie nerandomizate, dar pentru uşurinţa implementării vom folosi una randomizată.

== code(cpp) |
int  select(int n, int[] a, int left, int right, int k) {
    Random ran = new Random(System.currentTimeMilis());