|
题目描述：
我的解答：
class Solution {
//最简单的方法，分别从左边找和从右边找
public int[] searchRange(int[] nums, int target) {
int[] targetIndex = {-1, -1};
//从左边找
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
targetIndex[0] = i;
break;
}
}
// 如果左边没有，就说明nums中没有这个target
if (targetIndex[0] == -1) {
return targetIndex;
}
// 从右边开始找
for (int j = nums.length-1; j >= 0; j--) {
if (nums[j] == target) {
targetIndex[1] = j;
break;
}
}
return targetIndex;
}
}
运行结果：
另外一种方法：
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;
}
}
| 
转播
