剑指Offer题目笔记21（计数排序）

面试题74：

问题：

​ 输入一个区间的集合，将重叠的区间合并。

解决方案：

​ 先将所有区间按照起始位置排序，然后比较相邻两个区间的结束位置就能知道它们是否重叠。如果它们重叠就将它们合并，然后判断合并的区间是否和下一个区间重叠。重复这个过程，直到所有重叠区间都合并为止。

源代码：

class Solution {
    public int[][] merge(int[][] intervals) {
    	//按照起始位置排序
        Arrays.sort(intervals,(i1,i2) -> i1[0] - i2[0]);

        List<int[]> list = new ArrayList<>();
        int i = 0;
        while(i < intervals.length){
        	//前区间
            int[] temp = new int[]{intervals[i][0],intervals[i][1]};
            int j = i + 1;
            //判断是否存在后区间，存在则判断后区间起始位置是否小于或等于前区间的终止位置
            while(j < intervals.length && intervals[j][0] <= temp[1]){
            	//重叠区间的终止位置由前区间和后区间的终止位置的最大值决定
                temp[1] = Math.max(intervals[j][1],temp[1]);
                j++;
            }

            list.add(temp);
            i = j;
        }

        int[][] result = new int[list.size()][];
        return list.toArray(result);
    }
}

面试题75：

问题：

​ 输入两个数组arr1和arr2，将数组arr1中的数字按照数组arr2中的数字的相对顺序排序。如果数组arr1中的数字在arr2中没有出现，那么将这些数字按递归的顺序排在后面。

解决方案：

​ 使用计数排序。先统计arr1中的每个整数在数组中出现的次数记为counts，然后按照arr2的顺序将每个整数按照它出现的次数填入到数组中，扫描完arr2数组后，继续扫描counts数组，如果counts数组中出现整数出现次数不为0时，将每个整数按照它出现的次数填入到arr2数组中。

源代码：

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] counts = new int[1001];
        for(int num:arr1){
            counts[num]++;
        }

        int i = 0;
        //扫描arr2数组
        for(int num:arr2){
            while(counts[num] > 0){
                arr1[i++] = num;
                counts[num]--;
            }
        }
		//扫描counts数组
        for(int num = 0;num < counts.length;num++){
            while(counts[num] > 0){
                arr1[i++] = num;
                counts[num]--;
            }
        }

        return arr1;
    }
}