Java Lambda 表达式不为人熟知的知识点

栏目: Java · 发布时间: 5年前

内容简介: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 表达式造成了效率的差距。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法设计与分析

算法设计与分析

王红梅 / 清华大学 / 2006-7 / 23.00元

《算法设计与分析》(普通高校本科计算机专业特色教材精选)将计算机经典问题和算法设计技术很好地结合起来,系统地介绍了算法设计技术及其在经典问题中的应用。全书共12章,第1章介绍了算法的基本概念和算法分析方法,第2章从算法的观点介绍了NP完全理论,第3章~~第11章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术,第12章基于图灵机计算模型介绍......一起来看看 《算法设计与分析》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

随机密码生成器
随机密码生成器

多种字符组合密码

SHA 加密
SHA 加密

SHA 加密工具