一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1904|回复: 8
收起左侧

[算法题] palantir running median解法

[复制链接] |试试Instant~ |关注本帖
cocaptainco 发表于 2015-3-10 23:26:57 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近看到的palantir面经里基本都问这道题,双heap的做法我知道。关键是follow up的话,只能用constant memory 和只读 array,请问最优解是啥?
shawlin 发表于 2015-3-15 04:26:47 | 显示全部楼层
帮顶,同问!紫薯 紫薯
回复 支持 反对

使用道具 举报

zhuang1992 发表于 2015-3-15 04:37:39 | 显示全部楼层
我自己想了个方法,不确定是否是正解。

主要就是对于前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();
     }
}

欢迎交流。
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2015-3-15 09:13:29 | 显示全部楼层
嗯,我也觉得这样做比较靠谱
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-4-1 01:19:50 | 显示全部楼层
cocaptainco 发表于 2015-3-14 20:13
嗯,我也觉得这样做比较靠谱

LZ onsite了么?求面经啊
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2015-4-1 09:07:40 | 显示全部楼层
shawlin 发表于 2015-4-1 01:19
LZ onsite了么?求面经啊

嗯,我post过
回复 支持 反对

使用道具 举报

douya 发表于 2015-4-5 05:55:46 | 显示全部楼层
zhuang1992 发表于 2015-3-15 04:37
我自己想了个方法,不确定是否是正解。

主要就是对于前i个数字,记录它的median,最接近median且比media ...

但这样就不是无限输入流了吧?
输入得是个等于total的大小
回复 支持 反对

使用道具 举报

Annabelle哈哈哈 发表于 2015-4-5 06:02:46 | 显示全部楼层
问了个大神说counting sort, 常数级空间。没想太明白。
另外一种follow up就是说找最近K个的median, 想了想貌似要另外建一个类似LRU的东西,每次都要把最先进堆的给踢掉。
这个题被问到两次了,每次follow up都不一样,两次都没能好好说出来,主要是面试官给的提示相当有限=-=,胡说八道了一通也不知道面试官什么感想。
回复 支持 反对

使用道具 举报

xuepanchen 发表于 2015-6-25 09:38:15 | 显示全部楼层
Annabelle哈哈哈 发表于 2015-4-5 06:02
问了个大神说counting sort, 常数级空间。没想太明白。
另外一种follow up就是说找最近K个的median, 想了 ...

COUNTING SORT只适用于整数,如果是小数就不行了,要用的空间就是整个整数的范围。

请问找最近的K个MEDIAN有没有什么好的算法啊?除了每次都重新算一遍哈哈
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 01:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表