一亩三分地论坛

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

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

indeed OA#15 代码分享

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

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

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

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

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;
    . more info on 1point3acres.com
  7.         }. 鍥磋鎴戜滑@1point 3 acres
  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;. 1point3acres.com/bbs
  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);. visit 1point3acres.com for more.
  18.                 idx = (long)Math.ceil((double)N * ++k / Q);. from: 1point3acres.com/bbs
  19.             }
  20.             if(k == Q) break;
  21.         }
  22.         return result;. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.     }

  24.     public static void main(String[] args) {. 1point3acres.com/bbs
  25.         Scanner sc = new Scanner(System.in);
  26.         long Q = sc.nextInt();
  27.         int M = sc.nextInt();. more info on 1point3acres.com
  28.         long N = 0;
  29.         Pair[] pairs = new Pair[M];

  30.         for(int i = 0; i < M; i++){
  31.             pairs[i] = new Pair(sc.nextInt(), sc.nextInt());
  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.             }
  39.         });
  40. . visit 1point3acres.com for more.
  41.         List<Integer> result = findQuantiles(N, Q, M, pairs);. more info on 1point3acres.com
  42.         //System.out.println();
  43.         for(int res: result) System.out.print(res + " ");

  44.         sc.close();. Waral 鍗氬鏈夋洿澶氭枃绔,
  45.     }
复制代码

补充内容 (2016-2-17 03:29):
时间复杂度忘记考虑sort了,说错了,抱歉

评分

2

查看全部评分

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-26 18:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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