LeetCode 480. Sliding Window Median

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/01/18/LeetCode-480-Sliding-Window-Median/

访问原文「LeetCode 480. Sliding Window Median

题目要求

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, 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. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Median


[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

题意解析

假设现在存在一个数列,然后有一个滑动窗口,这个滑动窗口从这个数列的最左端开始向右滑动,求出所有在滑动窗口中的中位数。这里要注意的是,数列长度为偶数是,中位数是中间两个数和的一半。

解法分析

这道题首先初始化滑动窗口,假设滑动窗口的大小为K,则将滑动窗口中从左起的K个数放入滑动窗口中。然后将滑动窗口进行排序,这样可以算出来第一个中间值。然后开始滑动窗口,没滑动一次,将前一个窗口中的第一个数从滑动窗口中溢出,替代以新进入窗口的值,然后排序,这个时候的排序很简单,向前或者向后进行一次冒泡即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public double[] medianSlidingWindow(int[] nums, int k) {
if (k == 0 || k > nums.length) {
return new double[] {};
}
if (k == 1) {
double[] results = new double[nums.length];
for (int i = 0; i < nums.length; i++) {
results[i] = nums[i];
}
return results;
}
boolean isEven = k % 2 == 0;
double[] results = new double[nums.length - k + 1];
List<Integer> temps = new ArrayList<>();
for (int i = 0; i < k; i++) {
temps.add(nums[i]);
}
Collections.sort(temps);
if (isEven) {
results[0] = (long) temps.get(k / 2 - 1)
+ ((long) temps.get(k / 2) - (long) temps.get(k / 2 - 1))
/ 2.0;
} else {
results[0] = temps.get(k / 2);
}
for (int i = 1; i < nums.length - k + 1; i++) {
int index = temps.indexOf((Integer) nums[i - 1]);
temps.set(index, nums[k + i - 1]);
boolean isForward = index > 0
&& (nums[k + i - 1] < temps.get(index - 1));
if (isForward) {
for (int j = index; j >= 1; j--) {
int first = temps.get(j - 1);
int second = temps.get(j);
if (second < first) {
temps.set(j - 1, second);
temps.set(j, first);
} else {
break;
}
}
} else {
for (int j = index; j < temps.size() - 1; j++) {
int first = temps.get(j);
int second = temps.get(j + 1);
if (second < first) {
temps.set(j, second);
temps.set(j + 1, first);
} else {
break;
}
}
}
if (isEven) {
results[i] = (long) temps.get(k / 2 - 1)
+ ((long) temps.get(k / 2) - (long) temps
.get(k / 2 - 1)) / 2.0;
} else {
results[i] = temps.get(k / 2);
}
}
return results;
}