#40. Find Median from Data Stream
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. Implement the MedianFinder class.
// solutie cu sortare prin inserare, O(n^2)
class MedianFinder2 {
int[] values;
public MedianFinder2() {
values = null;
}
public void addNum(int num) {
insertAt(findIndex(num), num);
}
public double findMedian() {
int len = values.length;
if (len % 2 == 1) {
return Double.valueOf(values[len / 2]);
}
return (values[len/2-1] + values[len/2]) / 2.0;
}
private int findIndex(int value) {
if (values == null) {
return 0;
}
return findIndex(value, 0, values.length - 1);
}
private int findIndex(int value, int from, int to) {
if (from == to) {
return value >= values[from] ? from + 1 : from;
}
int mid = from + (to - from) / 2;
if (value <= values[mid]) {
return findIndex(value, from, mid);
}
return findIndex(value, mid+1, to);
}
private void insertAt(int index, int value) {
if (values == null) {
values = new int[1];
values[index] = value;
} else {
int [] copy = new int[values.length + 1];
System.arraycopy(values, 0, copy, 0, index);
System.arraycopy(values, index, copy, index+1, values.length - index);
copy[index] = value;
values = copy;
}
}
}
// solutie in O(n log n) folosind un max heap si un min heap
class MedianFinder {
Queue<Integer> qMin; // elem mai mici decat mediana, ordonate DESC
Queue<Integer> qMax; // elem mai mari decat mediana, ordonate ASC
public MedianFinder() {
qMin = new PriorityQueue<>(Collections.reverseOrder());
qMax = new PriorityQueue<>();
}
public void addNum(int num) {
if (qMin.isEmpty() && qMax.isEmpty()) {
qMin.add(num);
} else if (qMax.isEmpty()) {
int firstNum = qMin.poll();
qMin.add(Math.min(firstNum, num));
qMax.add(Math.max(firstNum, num));
} else {
if (num > qMin.peek()) {
qMax.add(num);
} else {
qMin.add(num);
}
while (qMin.size() - qMax.size() > 1) {
qMax.add(qMin.poll());
}
while (qMax.size() - qMin.size() > 1) {
qMin.add(qMax.poll());
}
}
}
public double findMedian() {
if (qMin.size() == qMax.size()) {
return (qMin.peek() + qMax.peek()) / 2.0;
}
if (qMin.size() > qMax.size()) {
return qMin.peek();
}
return qMax.peek();
}
}
Variatie: Sliding Window Median
You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the median array for each window in the original array.
// Time Limit Exceeded pt N=100k si k=50k !
class Solution {
Queue<Integer> qMin;
Queue<Integer> qMax;
private void initQueues() {
qMin = new PriorityQueue<>(Collections.reverseOrder());
qMax = new PriorityQueue<>();
}
private void addNum(int num) {
if (qMin.isEmpty() && qMax.isEmpty()) {
qMin.add(num);
} else if (qMax.isEmpty()) {
int firstNum = qMin.poll();
qMin.add(Math.min(firstNum, num));
qMax.add(Math.max(firstNum, num));
} else {
if (!qMin.isEmpty() && num > qMin.peek()) {
qMax.add(num);
} else {
qMin.add(num);
}
rebalance();
}
}
private void removeNum(int num) { // O(N) to remove an element from priority queue!
if (qMin.contains(num)) {
qMin.remove(num);
} else if (qMax.contains(num)) {
qMax.remove(num);
}
rebalance();
}
private void rebalance() {
while (qMin.size() - qMax.size() > 1) {
qMax.add(qMin.poll());
}
while (qMax.size() - qMin.size() > 1) {
qMin.add(qMax.poll());
}
}
private double findMedian() {
if (qMin.size() == qMax.size()) {
return (Long.valueOf(qMin.peek()) + Long.valueOf(qMax.peek())) / 2.0;
}
if (qMin.size() > qMax.size()) {
return qMin.peek();
}
return qMax.peek();
}
public double[] medianSlidingWindow(int[] nums, int k) {
Solution sol = new Solution();
sol.initQueues();
for (int i=0; i<k; i++) {
sol.addNum(nums[i]);
}
double[] result = new double[nums.length - k + 1];
result[0] = sol.findMedian();
for (int i=1; i<nums.length - k + 1; i++) {
sol.removeNum(nums[i-1]);
sol.addNum(nums[k + i - 1]);
result[i] = sol.findMedian();
}
return result;
}
}
Alta solutie:
Niciun comentariu:
Trimiteți un comentariu