436. Find Right Interval

题目链接：https://leetcode.cn/problems/find-right-interval/

方法一 二分查找

1 方法思想

1. 建立一个二维数组，其中存放所有interval中的数组索引为零的元素（起点），以及其数组在interval中的位置。并对该二维数组进行排序，方便进行二分查找。
2. 遍历interva数组中的最后一个元素X，找到在新建二维数组中大于X的最小数，其对应的interval下标就是结果，如果没有符合条件的元素，给答案赋值-1。

2 代码实现

class Solution {public int[] findRightInterval(int[][] intervals) {int len = intervals.length;int[][] startNums = new int[len][2];int[] ans = new int[len];for (int i = 0; i < len; i++) {startNums[i][0] = intervals[i][0];startNums[i][1] = i;}Arrays.sort(startNums, (a, b) -> a[0] - b[0]);for (int i = 0; i < len; i++) {int left = 0;int right = len - 1;int target = -1;while (left <= right) {int mid = left + (right - left) / 2;if (startNums[mid][0] >= intervals[i][1]) {target = startNums[mid][1];right = mid - 1;} else {left = mid + 1;}}ans[i] = target;}return ans;}}

3 复杂度分析

时间复杂度：O(n*log n)
空间复杂度：O(n)

4 涉及到知识点

二分查找：找到有序数组中大于等于X的最小元素位置。没有找到就返回-1。

int target = -1;
while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= key) {target = nums[mid];right = mid - 1;} else {left = mid + 1;}
}
ans = target;

二维数组排序，lamda表达式，根据二维数组的第一个元素进行升序排序。

	int[][] startNums = new int[len][2];Arrays.sort(startNums, (a, b) -> a[0] - b[0]);

方法二 双指针