找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 8028|回复: 4
收起左侧

[米群网刷题小分队] 【LeetCode刷题小分队】LC新题Maximum Gap O(N)(JAVA)

[复制链接]

84

主题

32

精华

1278

积分

顶级会员

Rank: 6Rank: 6

积分
1278

活跃会员热心会员最佳新人精华帖之王

发表于 12-15-2014 05:21 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

解法1:先排序再撸一遍,时间复杂度为O(NLogN),空间复杂度O(1)。
解法2:和曹神的解法一样。。。利用抽屉原理。n个数放进n+1个,必有一个抽屉为空。而且max gap的两个值必然在两个不同的抽屉里。
刚开始我把抽屉的delta向下取整了。。。所以不只n+1个抽屉。。。后来看到了曹神的c++版本,才知道其实非整型的抽屉也是可以过的。
不过如曹神所提醒的一样,JAVA也会出现int相乘溢出问题,所以要转换成Long。
时间复杂度O(n),空间复杂度O(n)


  1. public class Solution {
  2.     public int maximumGap_1(int[] num) {
  3.         Arrays.sort(num);
  4.         int res = 0;
  5.         for (int i = 1; i < num.length; ++i) {
  6.             res = Math.max(res, num【i】 - num[i - 1]);
  7.         }
  8.         return res;
  9.     }
  10.     class node {
  11.         public int low;
  12.         public int high;
  13.         public node() {
  14.             low = -1;
  15.             high = -1;
  16.         }
  17.     }
  18.     public int maximumGap(int[] num) {
  19.         int n = num.length;
  20.         if (n < 2) return 0;
  21.         int minVal = num[0], maxVal = num[0];
  22.         for (int i = 1; i < n; ++i) {
  23.             minVal = Math.min(minVal, num【i】);
  24.             maxVal = Math.max(maxVal, num【i】);
  25.         }
  26.         //delta = (maxVal + 1 - minVal) / (n + 1)
  27.         node[] pool = new node[n+2];
  28.         for (int i = 0; i < n+2; ++i) pool【i】 = new node();
  29.         for (int i = 0; i < n; ++i) {
  30.             int idx =(int)(Long.valueOf(num【i】 - minVal)* Long.valueOf(n + 1) / Long.valueOf(maxVal + 1 - minVal));
  31.             if (pool[idx].low == -1) {
  32.                 pool[idx].low = pool[idx].high = num【i】;
  33.             } else {
  34.                 pool[idx].low = Math.min(pool[idx].low, num【i】);
  35.                 pool[idx].high = Math.max(pool[idx].high, num【i】);
  36.             }
  37.         }
  38.         int last = pool[0].high;
  39.         int res = 0;
  40.         for (int i = 1; i < n + 2; ++i) {
  41.             if (pool【i】.low != -1) {
  42.                 res = Math.max(res, pool【i】.low - last);
  43.                 last = pool【i】.high;
  44.             }
  45.         }
  46.         return res;
  47.     }
  48. }

复制代码

本帖被以下淘专辑推荐:

发表于 12-15-2014 11:11 AM | 显示全部楼层
给个精华
回复

使用道具 举报

0

主题

0

精华

2

积分

新米人

Rank: 1

积分
2
发表于 12-17-2014 06:43 PM | 显示全部楼层
感谢分享楼主,对于提及的非正型抽屉我觉得虽然非整型抽屉可以过目前的test cases,但是我觉得有风险,毕竟浮点数运算造成的误差有可能会造成边界判断错误,还是整型的安全些,不知各位怎么看。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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