leetcode56.合并区间和发现的问题

leetcode56.合并区间和发现的问题

二月 23, 2020

leetcode56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

首先要明白一件事，按照区间左端点start排序之后，能合并的区间一定是连续的。这样就只用每次判断右端点是否满足条件就可以。
题只要理解了原理不难，但是我发现了一个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class cmp implements Comparator<int[]> {
//排序的方式，如果返回值小于0,说明a<b
		@Override
		public int compare(int[]a, int[]b) {
			// TODO Auto-generated method stub
			return a[0]-b[0];
		}
	}
    public int[][] merge(int[][] intervals) {
        if(intervals.length==0)return intervals;
		Arrays.sort(intervals,new cmp());
        int[] tmp=new int[2];
        ArrayList<int[]>list=new ArrayList<>();
        tmp[0]=intervals[0][0];
        tmp[1]=intervals[0][1];
        list.add(tmp);
        int left=0,right=0;
        for(int i=1;i<intervals.length;i++) {
        	left=list.get(list.size()-1)[0];
    		right=list.get(list.size()-1)[1];
        	if(intervals[i][0]>right) {
        		left=intervals[i][0];
        		right=intervals[i][1];
        		int[]p= {left,right};
        		//tmp[0]=left;
        		//tmp[1]=right;
        		list.add(p);
        	}else {
    			list.remove(list.size()-1);
        		right=Math.max(intervals[i][1],right);
        		//tmp[0]=left;
        		//tmp[1]=right;
        		int[]p= {left,right};
        		list.add(p);
        	}
        	/*for(int ii=0;ii<list.size();ii++) {
        		System.out.print("第"+i+"次"+"["+list.get(ii)[0]+","+list.get(ii)[1]+"],");
        	}*/
        }
        // int[][]result=new int[list.size()][2];
        // for(int i=0;i<list.size();i++){
        //     result[i][0]=list.get(i)[0];
        //     result[i][1]=list.get(i)[1];
        // }
        // return result;下面就能替代这一堆
        return list.toArray(new int[list.size()][2]);
    }

这里在我做题的过程中，开始我并没有用if-else里面的p数组，而是直接用了最外面的tmp，每次list.add(tmp),但是最后发现list里面存的值全都是一样的数组。
在这里插入图片描述
Debug模式下，在第二次循环结束后就已经不对劲了，我第一次存入的数组值怎么改变了呢。仔细观察右侧发现list存入的地址值是一样的，这么就说明：
list里面存放的是对象的引用。
这之后我做了一个实验：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.ArrayList;
import java.util.List;

class User{
	public String name;
	public int age;
}
public class test {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
			ArrayList<User>list=new ArrayList<>();
			User u=new User();
			u.name="aaa";
			u.age=12;
			list.add(u);
			System.out.println(list.get(0).name+"--"+list.get(0).age);
			//aaa--12
			u.name="bbb";
			u.age=20;
			list.add(u);
			System.out.println("第一次"+list.get(0).name+"--"+list.get(0).age);
			//第一次bbb--20
			System.out.println("第二次"+list.get(1).name+"--"+list.get(1).age);	
			//第二次bbb--20	
	}
}

说明list里面存放的的确是引用。
（刷题还刷出了原理，今天血赚）leetcode 17/100