转载

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

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) 复杂度的解法(当然还有常数级别的优化空间)，难道还能有更高效的做法？