题目
这是lintcode上的一道题,上次看别人发了后自己试着写了一下。感觉是比较没有技术含量的解题思路吧,而且上次面试时候也有遇到过,就当做个记录。
以下是题目:
·····································
给定一个包含 n 个整数的数组,和一个大小为 k 的滑动窗口,从左到右在数组中滑动这个窗口,找到数组中每个窗口内的中位数。(如果数组个数是偶数,则在该窗口排序数字后,返回第 N/2 个数字。)
样例
对于数组 [1,2,7,8,5], 滑动大小 k = 3 的窗口时,返回 [2,7,7]
最初,窗口的数组是这样的:
[ | 1,2,7 | ,8,5] , 返回中位数 2;
接着,窗口继续向前滑动一次。
[1, | 2,7,8 | ,5], 返回中位数 7;
接着,窗口继续向前滑动一次。
[1,2, | 7,8,5 | ], 返回中位数 7;
·····································
代码
import java.util.Comparator;
import java.util.List;
public class Solution {
public static void main(String[] args){
System.out.println(medianSlidingWindow(new int[]{1,2,7,7,2},3));
}
/**
* @param nums: A list of integers
* @param k: An integer
* @return: The median of the element inside the window at each moving
*/
public static List<Integer> medianSlidingWindow(int[] nums, int k) {
// write your code here
if (nums == null || nums.length == 0 || k <= 0)return new ArrayList<Integer>();
int left = 0;
int right = k -1;
List<Data> temp = new ArrayList<>();
List<Integer> result = new ArrayList<>();
for (int i = left;i<right;i++){
temp.add(new Data(i,nums[i]));
}
temp.sort(new MyCom());
int curLeft = 0;
for (;right < nums.length;left++,right++){
Data target = new Data(right,nums[right]);
boolean insertTarget = false,findPos = false;
for (int j = 0;j<temp.size();j++){
Data data = temp.get(j);
if (data.value >=target.value && !insertTarget){
temp.add(j,target);
j++;
insertTarget = true;
}
if (data.pos == left && !findPos){
curLeft = j;
findPos = true;
}
if (insertTarget && findPos)break;
}
if (!insertTarget)
temp.add(target);
result.add(temp.get((temp.size()-1) / 2).value);
temp.remove(curLeft);
}
return result;
}
static class Data{
public Data(int pos,int value){
this.pos = pos;
this.value = value;
}
int pos;
int value;
}
static class MyCom implements Comparator<Data> {
@Override
public int compare(Data o1, Data o2) {
if (o1.value > o2.value)return 1;
if (o1.value == o2.value)return 0;
return -1;
}
@Override
public boolean equals(Object obj) {
return false;
}
}
}