一定要早日上岸鸭 · July 16, 2021 0

436. 寻找右区间

436. 寻找右区间

class Solution { public int[] findRightInterval(int[][] intervals) { int N = intervals.length; // 将原数组拷贝进新数组,且新数组用额外一个元素来储存下标 for(int i = 0; i<N; i++){ intervals[i] = new int[]{intervals[i][0], intervals[i][1], i}; } // 按照左端点(行)排序, 记住: Arrays.sort(intervals, Comparator.comparingInt(o -> o[0])); // deepToString可以用来print多维数组 System.out.println(Arrays.deepToString(intervals)); // 创建res 数组来存储结果,注意结果为对应下标 int[] res= new int[N]; // 初始化为负一因为当不存在右区间时结果为-1 Arrays.fill(res,-1); // 枚举每一个区间 for(int i = 0; i<N; i++){ // 二分查找看枚举的区间是否有右区间 int l = 0, r = N-1; while(l<r){ int mid = l+r>>1; // 若左端点大于暂时目标的右端点,说明目标在左侧 // 目标就是intervals[i][1]也就是最小的右区间 if(intervals[mid][0]>=intervals[i][1]) r = mid; else l = mid + 1; } System.out.println(r); // 若找到的目标的左端点大于枚举目标的右端点,则说明右区间存在 // 将对应的下标存入原本区间所在的位置 if(intervals[r][0]>=intervals[i][1]) res[intervals[i][2]] = intervals[r][2]; } return res; } }