📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3879| 回复: 9
跳转到指定楼层
上一主题 下一主题
收起左侧

palantir running median解法

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
最近看到的palantir面经里基本都问这道题,双heap的做法我知道。关键是follow up的话,只能用constant memory 和只读 array,请问最优解是啥?

上一篇:求大牛指点leetcode的部分题目。
下一篇:Leetcode 4 Sum
🔗
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的大小
回复

使用道具 举报

🔗
65岁退休 2015-4-5 06:02:46 | 只看该作者
全局:
问了个大神说counting sort, 常数级空间。没想太明白。
另外一种follow up就是说找最近K个的median, 想了想貌似要另外建一个类似LRU的东西,每次都要把最先进堆的给踢掉。
这个题被问到两次了,每次follow up都不一样,两次都没能好好说出来,主要是面试官给的提示相当有限=-=,胡说八道了一通也不知道面试官什么感想。
回复

使用道具 举报

🔗
xuepanchen 2015-6-25 09:38:15 | 只看该作者
全局:
65岁退休 发表于 2015-4-5 06:02
问了个大神说counting sort, 常数级空间。没想太明白。
另外一种follow up就是说找最近K个的median, 想了 ...

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

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

使用道具 举报

🔗
liuxu1005 2018-3-28 19:54:39 | 只看该作者
全局:
我想看看答案:)
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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