中位数是有序序列最中间的那个数。如果序列的长度是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。
例如:
[2,3,4],中位数是 3
[2,3],中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums,有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数,每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数,并输出由它们组成的数组。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sliding-window-median
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
class Solution {
public static double[] medianSlidingWindow(int[] nums, int k) {
Heap leftHeap = new Heap(nums.length, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Integer.compare(o2, o1);
}
});
Heap rightHeap = new Heap(nums.length, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Integer.compare(o1, o2);
}
});
int base = nums[0];
double[] ret = new double[nums.length - k + 1];
for (int i = 0; i < nums.length; ++i) {
if (nums[i] <= base) {
leftHeap.offer(i, nums[i]);
if (leftHeap.size() > rightHeap.size() + 1) {
int[] pop = leftHeap.pop();
rightHeap.offer(pop[0], pop[1]);
}
} else {
rightHeap.offer(i, nums[i]);
if (rightHeap.size() > leftHeap.size()) {
int[] pop = rightHeap.pop();
leftHeap.offer(pop[0], pop[1]);
}
}
base = leftHeap.peek()[1];
if (i + 1 >= k) {
if (k % 2 == 0) {
ret[i + 1 - k] = ((long)leftHeap.peek()[1] + rightHeap.peek()[1]) / 2.0;
} else {
ret[i + 1 - k] = leftHeap.peek()[1];
}
leftHeap.remove(i + 1 - k);
rightHeap.remove(i + 1 - k);
}
}
return ret;
}
public static void main(String[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
double[] ret = medianSlidingWindow(nums, k);
Arrays.stream(ret).forEach(System.out::println);
}
}
class Heap {
private Comparator<Integer> comparator;
private Map<Integer, Integer> rawIndex2HeapIndexMap;
private Map<Integer, Integer> heapIndex2RawIndexMap;
private int size;
private int[] data;
public Heap(int limit, Comparator<Integer> comparator) {
this.size = 0;
this.data = new int[limit + 1];
this.comparator = comparator;
this.rawIndex2HeapIndexMap = new HashMap<>();
this.heapIndex2RawIndexMap = new HashMap<>();
}
private int left(int index) {
return index << 1;
}
private int right(int index) {
return index << 1 | 1;
}
private int parent(int index) {
return index >> 1;
}
private void swap(int a, int b) {
int rawIndexOfA = heapIndex2RawIndexMap.get(a);
int rawIndexOfB = heapIndex2RawIndexMap.get(b);
int tmp = data[a];
data[a] = data[b];
data[b] = tmp;
rawIndex2HeapIndexMap.put(rawIndexOfA, b);
rawIndex2HeapIndexMap.put(rawIndexOfB, a);
heapIndex2RawIndexMap.put(a, rawIndexOfB);
heapIndex2RawIndexMap.put(b, rawIndexOfA);
}
private void heapifyUp(int index) {
int parent;
while (index != 1) {
parent = parent(index);
if (comparator.compare(data[index], data[parent]) < 0) {
swap(index, parent);
} else {
break;
}
index = parent;
}
}
private void heapifyDown(int index) {
int left, right;
while ((left = left(index)) <= size) {
int bestIndex = index;
if (comparator.compare(data[left], data[bestIndex]) < 0) {
bestIndex = left;
}
if ((right = right(index)) <= size && comparator.compare(data[right], data[bestIndex]) < 0) {
bestIndex = right;
}
if (bestIndex == index) {
break;
}
swap(bestIndex, index);
index = bestIndex;
}
}
public int size() {
return size;
}
public void offer(int rawIndex, int ele) {
size++;
data[size] = ele;
rawIndex2HeapIndexMap.put(rawIndex, size);
heapIndex2RawIndexMap.put(size, rawIndex);
heapifyUp(size);
}
public int[] peek() {
return new int[]{heapIndex2RawIndexMap.get(1), data[1]};
}
public int[] pop() {
return pop(heapIndex2RawIndexMap.get(1));
}
public int[] pop(int rawIndex) {
int heapIndex = rawIndex2HeapIndexMap.get(rawIndex);
swap(heapIndex, size);
int ret = data[size];
rawIndex2HeapIndexMap.remove(rawIndex);
heapIndex2RawIndexMap.remove(size);
size--;
heapifyUp(heapIndex);
heapifyDown(heapIndex);
return new int[]{rawIndex, ret};
}
public void remove(int rawIndex) {
if (rawIndex2HeapIndexMap.containsKey(rawIndex)) {
pop(rawIndex);
}
}
}