自己解法
又是二分查找，这个题很简单的想法就是用二分查找，但是呢，具体实现的时候思路有点混乱，找到第一个target的点以后不知道怎么操作了，想用递归发现合并非常复杂，思路应该是错了，就看了下官方的题解，基本就是先用二分去找左边界，再找一遍右边界，也算是很直接了，不过自己没想到，下面上代码。
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = {-1, -1};
if (nums.length == 0) {
return res;
}
// 先求左边界
int left = getBoundIndex(nums, target, true);
if (nums[left] != target) {
return res;
}
int right = getBoundIndex(nums, target, false);
res[0] = left;
res[1] = right;
return res;
}
private int getBoundIndex(int[] nums, int target, boolean flag) {
int left = 0;
int right = nums.length - 1;
int res = flag ? right : left;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
if (flag) {
res = Math.min(res, mid);
right = mid - 1;
} else {
res = Math.max(res, mid);
left = mid + 1;
}
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return res;
}
}
官方解法
官方解法的思路完全一样，取边界值更简单，但没那么好理解，贴出吧。
class Solution {
// returns leftmost (or rightmost) index at which `target` should be
// inserted in sorted array `nums` via binary search.
private int extremeInsertionIndex(int[] nums, int target, boolean left) {
int lo = 0;
int hi = nums.length;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] > target || (left && target == nums[mid])) {
hi = mid;
}
else {
lo = mid+1;
}
}
return lo;
}
public int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1, -1};
int leftIdx = extremeInsertionIndex(nums, target, true);
// assert that `leftIdx` is within the array bounds and that `target`
// is actually in `nums`.
if (leftIdx == nums.length || nums[leftIdx] != target) {
return targetRange;
}
targetRange[0] = leftIdx;
targetRange[1] = extremeInsertionIndex(nums, target, false)-1;
return targetRange;
}
}
网友评论