前言
一个多月没有更新了。
正文
问题来源
本问题来自leetcode上的34题。
问题描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
分析：
这道题不能用go来提交
func searchRange(nums []int, target int) []int {
res := make([]int, 2)
res[0], res[1] = -1, -1
if len(nums) == 0 || nums[0] > target || nums[len(nums)-1] < target {
return res
}
l := 0; r := len(nums) -1
for l <= r {
mid := (l+r) / 2
if nums[mid] > target {
r = mid - 1
} else if nums[mid] < target {
l = mid + 1
} else {
i := mid
for ; i >= 0 && nums[i] == target ; i-- {
}
res[0] = i + 1
i = mid
for ; i < len(nums) && nums[i] == target; i++ {
}
res[1] = i - 1
return res
}
}
return res
}
别人的代码
public class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
int index = searchRightIndex(nums, 0, nums.length - 1, target);
if (index < 0 || nums[index] != target)
return result;
result[0] = searchLeftIndex(nums, 0, index, target);
result[1] = index;
return result;
}
public int searchRightIndex(int[] nums, int left, int right, int target) {
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target) right = mid - 1;
else left = mid + 1;
}
return right;
}
public int searchLeftIndex(int[] nums, int left, int right, int target) {
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
}
递归实现
public class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
res[0] = bSearchLeft(nums, target, 0, nums.length-1);
res[1] = bSearchRight(nums, target, 0, nums.length-1);
return res;
}
private int bSearchLeft(int[] nums, int target, int left, int right) {
if(left > right) return (left < nums.length && nums[left] == target) ? left : -1;
int mid = (left + right) / 2;
if(nums[mid] < target) return bSearchLeft(nums, target, mid+1, right);
else return bSearchLeft(nums, target, left, mid - 1);
}
private int bSearchRight(int[] nums, int target, int left, int right) {
if(left > right) return (right >= 0 && nums[right] == target) ? right : -1;
int mid = (left + right) / 2;
if(nums[mid] > target) return bSearchRight(nums, target, left, mid-1);
else return bSearchRight(nums, target, mid+1, right);
}
}
总结：
勤思考。
结语
不管怎么样好好加油。
