剑指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;}
}