Find First and Last Position of Element in Sorted Array (M)
題目
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given targetvalue.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
題意
在給定的遞增陣列中找到目標值出現的第一個位置和最后一個位置，未找到目標值則回傳[-1, -1]，
思路
查找第一個位置時，通過二分法找到目標值后，先向左遞回看左側是否仍存在目標值，存在則回傳遞回值，不存在則回傳當前值；同理可查找最后一個位置，
代碼實作
Java
class Solution {
public int[] searchRange(int[] nums, int target) {
// 當不存在目標值時，必然有 first = last = -1
int first = binarySearch(nums, 0, nums.length - 1, target, true);
int last = first == -1 ? -1 : binarySearch(nums, 0, nums.length - 1, target, false);
return new int[]{first, last};
}
private int binarySearch(int[] nums, int left, int right, int target, boolean findLeft) {
while (left <= right) {
int mid = (left + right) / 2;
if (target < nums[mid]) {
right = mid - 1;
} else if (target > nums[mid]) {
left = mid + 1;
} else {
int value;
// 每次先判斷在左/右側是否仍存在目標值
if (findLeft) {
value = https://www.cnblogs.com/mapoos/p/binarySearch(nums, left, mid - 1, target, true);
} else {
value = binarySearch(nums, mid + 1, right, target, false);
}
return value == -1 ? mid : value;
}
}
return -1;
}
}
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
let left = 0, right = nums.length - 1
let res = []
// 找出現的第一個位置
while (left < right) {
let mid = Math.trunc((right - left) / 2) + left
if (nums[mid] === target) {
right = mid
} else if (nums[mid] < target) {
left = mid + 1
} else {
right = mid - 1
}
}
if (nums[left] !== target) {
return [-1, -1]
}
res.push(left)
// 找出現的最后一個位置
left = 0, right = nums.length
while (left < right) {
let mid = Math.trunc((right - left) / 2) + left
if (nums[mid] > target) {
right = mid
} else {
left = mid + 1
}
}
res.push(left - 1)
return res
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/38862.html
標籤：其他
上一篇：0287. Find the Duplicate Number (M)
下一篇：誰有這款軟體么