中级农民
- 积分
- 289
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2013-1-14
- 最后登录
- 1970-1-1
|
我自己想了个方法,不确定是否是正解。
主要就是对于前i个数字,记录它的median,最接近median且比median大,最接近median且比median小,这三个数。每添加一个新数进来,新的median必定是这三个数中的一个。比较这个新数与之前median的关系,再结合当前有奇数个还是偶数个数元素,可以判断下一个median应该是哪个数。维护median两侧的数需要O(n)的时间,因此每找一个median,都需要O(n)的时间。
附代码:
public class Solution {
public void onlineMedian(){
int cnt = 0;
int total = 10;
Scanner in = new Scanner(System.in);
int nums[] = new int[total];
//int median[] = new int[total];
int lastMedian = -1;
int lastMedianUp = -1;
int lastMedianDown = -1;
while(cnt < total){
int num = in.nextInt();
nums[cnt] = num;
int curMedian = -1;
if(cnt == 0){
curMedian = num;
//median[cnt] = curMedian;
lastMedian = curMedian;
System.out.println(curMedian);
cnt++;
continue;
}
if(num > lastMedian){
if((cnt+1)%2==0){
curMedian = lastMedian;
}else{
curMedian = lastMedianUp==-1?lastMedian:lastMedianUp;
}
}else if(num < lastMedian){
if((cnt+1)%2==1)
curMedian = lastMedian;
else
curMedian = lastMedianDown==-1?num:lastMedianDown;
}else{
curMedian = lastMedian;
}
//median[cnt] = curMedian;
lastMedian = curMedian;
lastMedianDown = getMedianDown(nums,cnt,curMedian);
lastMedianUp = getMedianUp(nums,cnt,curMedian);
System.out.println(curMedian);
cnt++;
}
}
int getMedianDown(int[]nums,int cnt, int median){
int minDiff = 99999;
int rst = -1;
for(int i = 0; i <= cnt; i++){
if(nums[i]<median && median-nums[i] < minDiff){
minDiff = median-nums[i];
rst = nums[i];
}
}
return rst;
}
int getMedianUp(int[]nums,int cnt, int median){
int minDiff = 99999;
int rst = -1;
for(int i = 0; i <= cnt; i++){
if(nums[i]>median && nums[i]-median < minDiff){
minDiff = nums[i]-median;
rst = nums[i];
}
}
return rst;
}
public static void main(String[] args){
Solution test = new Solution();
test.onlineMedian();
}
}
欢迎交流。 |
|