题目详情
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
**输入：** nums = [5,7,7,8,8,10], target = 8
**输出：** [3,4]
示例 2：
**输入：** nums = [5,7,7,8,8,10], target = 6
**输出：** [-1,-1]
示例 3：
**输入：** nums = [], target = 0
**输出：** [-1,-1]
提示：
0-109-
nums是一个非递减数组 -109
解题思路
方法1 线性查找
首先，我们从左边对nums进行线性扫描，当我们找到一个目标实例时就会中断。如果我们从不中断，那么目标就不存在，所以我们可以提前返回“-1，-1”的“错误代码”。考虑到我们确实找到了一个有效的左索引，我们可以进行第二次线性扫描，但这次从右开始。在这种情况下，遇到的目标的第一个实例将是最右边的实例（并且由于存在最左边的实例，因此也保证存在最右边的实例）。然后我们简单地返回一个包含两个定位索引的列表。
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1, -1};
// find the index of the leftmost appearance of `target`.
for (int i = 0; i = 0; j--) {
if (nums[j] == target) {
targetRange[1] = j;
break;
}
}
return targetRange;
}
}方法二 二分查找
除了用于查找左右索引本身的子例程之外，整体算法与线性扫描方法的工作方式非常相似。,在这里，我们使用修改后的二分查找来搜索已排序的数组，并进行一些小的调整。,首先，因为我们正在定位包含目标的最左边（或最右边）索引（而不是在我们找到目标时返回true），所以算法一找到匹配就不会终止。,相反，我们继续搜索直到lo == hi并且它们包含可以找到目标的索引。
,另一个变化是引入了左参数，这是一个布尔值，表示在target == nums [mid]的事件中要做什么;,如果左边是真的，那么我们在关系上的左子数组上“递归”,否则，我们在右子数组上递归。要了解为什么这是正确的，请考虑我们在索引i处找到目标的情况。,最左边的目标不能出现在大于i的任何索引处，因此我们永远不需要考虑正确的子阵列。,相同的参数适用于最右边的索引。
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 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;
}
}社区最佳答案
编程语言：java
运行时间：4ms
战胜比例：beat 100%
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = 0, end = nums.length - 1;
int[] res = new int[2];
Arrays.fill(res, -1);
while (start target) {
end = mid - 1;
}
// if (nums[start] == target && res[0] == -1) {
// res[0] = start;
// while (mid target) {
// end = temp - 1;
// }
//
// if (temp == mid
// || nums[temp] == target && (temp + 1 >= nums.length || nums[temp + 1] > target)) {
// res[1] = temp;
// break;
// } else if (temp == end) {
// end--;
// }
// }
//
// return res;
}
}
return res;
}
private int findFirst(int[] nums, int start, int end, int target) {
while (start target) {
end = temp - 1;
} else if (nums[temp] == target) {
start = temp;
}
}
return start;
}
}编程语言：javascript
运行时间：52ms
战胜比例：beat 100%
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
let searchRange = function(nums, target) {
let sl = 0;
let sm = 0;
let sr = nums.length - 1;
let el = 0;
let em = 0;
let er = nums.length - 1;
while (sl target) {
er = em - 1;
} else {
el = em;
}
}
}
return nums[sl] === target ? [sl, er] : [-1, -1];
};编程语言：python
运行时间：24ms
战胜比例：beat 100%
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return [-1, -1]
left = 0
right = len(nums) - 1
while left = 0 and nums[left] == target:
left -= 1
while right target:
right = mid - 1
else:
left = mid + 1
return [-1,-1]
编程语言：python3
运行时间：40ms
战胜比例：beat 100%
class Solution:
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
def binary_find(nums,left,right,k):
res = [-1,-1]
if not nums:return res
while leftk:
right -=1
elif nums[mid]编程语言：cpp
运行时间：4ms
战胜比例：beat 100%
static const auto _____ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
vector searchRange(vector& nums, int target) {
vector resultVec(2, -1);
int indexPre;
if ((resultVec[0] = Findpre(nums, target)) != -1) {
resultVec[1] = FindLast(nums, target);
}
return resultVec;
}
int Findpre(vector&nums, int target) {
int low = 0;
int high = nums.size() - 1;
while (low target)
high = middle - 1;
if (nums[middle] == target) {
if (middle - 1 == -1 || nums[middle - 1]&nums, int target) {
int low = 0;
int high = nums.size() - 1;
while (low target)
high = middle - 1;
if (nums[middle] == target) {
if (middle + 1 == nums.size() || nums[middle + 1]>target)
return middle;
else {
low = middle + 1;
}
}
}
return -1;
}
};编程语言：c
运行时间：4ms
战胜比例：beat 100%
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int *res;
*returnSize = 2;
res = (int*)malloc(sizeof(int) * 2);
res[0] = -1;
res[1] = -1;
int i;
int flag = 0; //开始标志
for (i = 0; i target)) {
*(res + 1) = i;
break;
}
}
return res;
}编程语言：swift
运行时间：16ms
战胜比例：beat 100%
class Solution {
func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
var left = 0
var right = nums.count - 1
var mid = 0
var first = -1
// 寻找第一个出现target的位置
while left = target {
right = mid - 1
} else {
left = mid + 1
}
if nums[mid] == target {
first = mid
}
}
// 如果找不到第一个直接返回
if first == -1 {
return [first ,first]
}
// 寻找最后一个出现target的位置
var last = -1
left = first
right = nums.count - 1
while left target {
right = mid - 1
} else {
left = mid + 1
}
if nums[mid] == target {
last = mid
}
}
return [first,last]
}
}参考资料
文内各种编程语言的最佳答案参考自 “算法面试宝典” 小程序，小程序内每个题目都有详细的解题报告，还有大厂面试真题，值得一用。wx扫码可打开。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
