1
$\begingroup$

If array is sorted we can generally find median in O(1) by returning the element at the middle. But what if there are duplicates?

E.g [2, 2, 3, 3, 3, 3]

$\endgroup$
  • 2
    $\begingroup$ The same. And when the length is even there are various definitions: return mean of teo middle elements or the lower (upper) one to keep median as element of the set. There is no definition depending on elements in the array. $\endgroup$ – Evil Oct 19 '16 at 23:47
  • 2
    $\begingroup$ Now, if you wanted median(set(input)), rather than median(input), then things would be significantly harder. ​ ​ $\endgroup$ – user12859 Oct 20 '16 at 3:11
1
$\begingroup$

Yes. Even with duplicates, the process of finding median is same. See this link - https://math.stackexchange.com/questions/1191119/how-to-find-the-median-of-three-numbers-if-one-of-them-appears-twice

$\endgroup$
  • 1
    $\begingroup$ How does that link help answering the question? $\endgroup$ – Raphael Oct 20 '16 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.