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]
$\begingroup$
$\endgroup$
2
-
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– Evil2016-10-19 23:47:11 +00:00Commented Oct 19, 2016 at 23:47
-
2$\begingroup$ Now, if you wanted median(set(input)), rather than median(input), then things would be significantly harder. $\endgroup$user12859– user128592016-10-20 03:11:27 +00:00Commented Oct 20, 2016 at 3:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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
-
1$\begingroup$ How does that link help answering the question? $\endgroup$Raphael– Raphael2016-10-20 09:10:39 +00:00Commented Oct 20, 2016 at 9:10