内容简介:Lambda 表达式是 Java 8 的新语法,可以极大地简化代码,增强语言的表达力。这里不赘述 Lambda 表达式的语法,主要从一道题目出发来说 Lambda 表达式的一个特性。从前阵子开始,坚持每天在 LeetCode 做一道题。这是前话。今天在做这道题的时候,碰到一个问题,记录下来备忘。题目本身很好理解:给几个区间,将其中重叠相交的合并,返回合并后的区间。
Lambda 表达式是 Java 8 的新语法,可以极大地简化代码,增强语言的表达力。这里不赘述 Lambda 表达式的语法,主要从一道题目出发来说 Lambda 表达式的一个特性。
从前阵子开始,坚持每天在 LeetCode 做一道题。这是前话。今天在做这道题的时候,碰到一个问题,记录下来备忘。
从题目说起
题目本身很好理解:给几个区间,将其中重叠相交的合并,返回合并后的区间。
做法也不难:将区间按照"起点小的在前,起点一样的则终点小的在前"排序。
选定第一个区间 A,按序依次遍历剩下的区间 B,如果 B 的起点比 A 的终点小,则 A 和 B 可以合并。
不断重复这个选定第一个区间的操作,直至将所有可合并的区间进行合并。
最后返回剩下的区间即可。
按理说不难,做完之后,也能通过了。代码如下:
public int[][] merge(int[][] intervals) { Arrays.sort(intervals,new Comparator<int[]>(){ public int compare(int a[],int b[]){ if(a[0]==b[0])return a[1]-b[1]; return a[0]-b[0]; } }); boolean[] vis = new boolean[intervals.length]; Arrays.fill(vis, true); for (int i = 0; i < intervals.length; i++) { if (!vis[i]) { continue; } for (int j = i + 1; j < intervals.length; j++) { if (intervals[j][0] <= intervals[i][1]) { vis[j] = false; if (intervals[i][1] < intervals[j][1]) { intervals[i][1] = intervals[j][1]; } } } } int count = 0; for (boolean v : vis) { if (v) { count++; } } int[][] ans = new int[count][2]; for (int i = 0, j = 0; i < intervals.length; i++) { if (!vis[i]) { continue; } ans[j++] = intervals[i]; } return ans; } 复制代码
不太理解的是 LeetCode 上的执行时间是 84 ms, 已经战胜 28.32 % 的 java 提交记录
。我左思右想,这已经是 O(N) 复杂度的解法(当然还有常数级别的优化空间),难道还能有更高效的做法?
效率差距的疑惑
于是我看了一下别人的解法,大体上是一样的,复杂的也是 O(N)。因为一些细节上的处理,会有常数级别的差距,但应该不至于有这么大的差距才对。
一开始怀疑是数据量很大,在遍历的过程需要访问当前数据和之前的数据,可能是在这时发生了取数据的耗时操作。于是尝试把需要比较的数据用临时变量存储下来。结果发现耗时并没有什么变化。
最后实在想不出来,于是照着别人的代码,一点点改,边改边看执行时间。
最后发现是 排序 这里的 lambda 表达式造成了效率的差距。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。