推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1473|回复: 0
收起左侧

indeed OA#15 代码分享

[复制链接] |试试Instant~ |关注本帖
一岁上山采药 发表于 2016-2-17 03:27:40 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Indeed - 网上海投 - 在线笔试 |Passfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
上一个帖子(传送门)说到楼主用了一个非二分法做indeed的OA#15,时间复杂度O(m+n),今天收到通过的邮件,把代码贴出来大家参考参考。求版主赏点大米
  1.     static class Pair{
  2.         int val;
  3.         int count;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.         public Pair(int val, int count){
  5.             this.val = val;
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.             this.count = count; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.         }
  8.     }

  9.     private static List<Integer> findQuantiles(long N, long Q, int M, Pair[] pairs){
  10.         List<Integer> result = new LinkedList<Integer>();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.         long sum = 0, k = 1;
  12.         long idx = (long)Math.ceil((double)N * k / Q);.鐣欏璁哄潧-涓浜-涓夊垎鍦

  13.         for(int i = 0; i < M; i++){
  14.             sum += pairs[i].count; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.             while(k <= Q - 1 && idx <= sum){
  16.                 //System.out.print(idx + " ");
  17.                 result.add(pairs[i].val);. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.                 idx = (long)Math.ceil((double)N * ++k / Q);
  19.             }
  20.             if(k == Q) break;
  21.         }
  22.         return result;
  23.     }

  24.     public static void main(String[] args) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  25.         Scanner sc = new Scanner(System.in);
  26.         long Q = sc.nextInt();
  27.         int M = sc.nextInt();
  28.         long N = 0;
  29.         Pair[] pairs = new Pair[M];

  30.         for(int i = 0; i < M; i++){. From 1point 3acres bbs
  31.             pairs[i] = new Pair(sc.nextInt(), sc.nextInt());-google 1point3acres
  32.             N += pairs[i].count;
  33.         }

  34.         Arrays.sort(pairs, new Comparator<Pair>(){
  35.             @Override. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  36.             public int compare(Pair p1, Pair p2){
  37.                 return p1.val - p2. val;
  38.             }. 鍥磋鎴戜滑@1point 3 acres
  39.         });. visit 1point3acres.com for more.
  40. . Waral 鍗氬鏈夋洿澶氭枃绔,
  41.         List<Integer> result = findQuantiles(N, Q, M, pairs);
  42.         //System.out.println();
  43.         for(int res: result) System.out.print(res + " ");

  44.         sc.close();. more info on 1point3acres.com
  45.     }
复制代码

补充内容 (2016-2-17 03:29):.鐣欏璁哄潧-涓浜-涓夊垎鍦
时间复杂度忘记考虑sort了,说错了,抱歉

评分

2

查看全部评分

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-18 09:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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