electroRF
Member
Hi,
I ran into this question: write a function that receives an array of n numbers and finds min, max, median and average.
You can of course sort the array in O(nlog(n)) and then get the min, max, median and average.
I wanna do it in O(n) though.
I thought of finding the Median using Quick Sort Algorithm to find the (n/2)th element, which would take O(n) on average, or O(n^2) on worst case.
I also know of the Median of Median algorithm which finds the median in O(n) worst case.
Is there any better way you know to find the min, max, median and average?
I ran into this question: write a function that receives an array of n numbers and finds min, max, median and average.
You can of course sort the array in O(nlog(n)) and then get the min, max, median and average.
I wanna do it in O(n) though.
I thought of finding the Median using Quick Sort Algorithm to find the (n/2)th element, which would take O(n) on average, or O(n^2) on worst case.
I also know of the Median of Median algorithm which finds the median in O(n) worst case.
Is there any better way you know to find the min, max, median and average?