Given a list of numbers, the median represents an important value in statistics,
ID: 3676604 • Letter: G
Question
Given a list of numbers, the median represents an important value in statistics, as it sits in the middle with as many elements below it as those above it. Develop and present an algorithm to find the median in an array of three or more integers. Test your algorithm in Java at
http://codingbat.com/prob/p285234
Determine and show the range for the number of element comparisons performed by your algorithm for an input list of n elements. Any summation should be reduced to a formula if possible.
Do you have any other idea that can be used to find the median? Particularly, can you think of any way to reduce the number of element comparisons used in your solution?
Important Note: Please do not use sorting as a solution to this problem.
Submission Requirement:
Submit your algorithm in Java as text on Blackboard. Your method should use the signature as follows:
public int median(int[] nums) {
}
Explanation / Answer
-------------------------------------------------------------------------------------------------------------------------------------------
public class Solution {
public int[] medianII(int[] nums) {
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
class maxComparator implements Comparator<Integer> {
public int compare(Integer a, Integer b) {
return Integer.compare(b, a);
}
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(nums.length, new maxComparator());
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (minHeap.size() < maxHeap.size()) {
if (nums[i] < maxHeap.peek()) {
minHeap.offer(maxHeap.poll());
maxHeap.offer(nums[i]);
} else {
minHeap.offer(nums[i]);
}
} else {
if (minHeap.size() > 0 && nums[i] > minHeap.peek()) {
maxHeap.offer(minHeap.poll());
minHeap.offer(nums[i]);
} else {
maxHeap.offer(nums[i]);
}
}
result[i] = maxHeap.peek();
}
return result;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.