34. 在排序数组中查找元素的第一个和最后一个位置

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

本题来自 LeetCode:34. 在排序数组中查找元素的第一个和最后一个位置[1]

题目描述

给定一个按照升序排列的整数数组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]

题目分析

由于题目要求时间复杂度为O(log n),因此不能通过线性遍历的方式来解答。需要通知分治的方式来进行剪枝。和53.最大子序和(点击查看) 的分治法解法类似。

  1. 通过分治法,将数组分成nums[left...mid]nums(mid...right]两个数组;
  2. target出现的地方有以下三种可能:
    a. 完全在左半部分nums[left...mid],那么需要查找左半部分即可;
    b. 完全在右半部分nums[mid...right],那么需要查找右半部分即可;
    c. 左右部分均包括target,那么可直接遍历得到起始位置和结束位置。

二分法(递归)

class Solution {

public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = -1;
result[1] = -1;

binarySearch(nums, target, 0, nums.length - 1, result);
return result;
}

public void binarySearch(int[] nums, int target, int left, int right, int[] result) {
if(left > right) {
return;
}
int mid = (left + right) >> 1;
if(nums[mid] < target) {
// 右半部分继续搜索
binarySearch(nums, target, mid + 1, right, result);
} else if(nums[mid] > target) {
// 左半部分继续搜索
binarySearch(nums, target, left, mid - 1, result);
} else {
// 左右部分均有
// 则直接从当前位置,查找最左边的目标值
int first = mid;
while(first >= left && nums[first] == target) {
result[0] = first --;
}
// 则直接从当前位置,查找最右边的目标值
int last = mid;
while(last <= right && nums[last] == target) {
result[1] = last++;
}
}
}
}

复杂度分析
时间复杂度:O(log(n))
空间复杂度:O(log(n));采用了递归

分治法(迭代)

递归版本的解法的空间复杂度为O(log(n)),可以通过迭代将空间复杂度降到O(1)

class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = -1;
result[1] = -1;

int left = 0;
int right = nums.length -1;
while(left <= right) {
int mid = (left + right) >> 1;
if(nums[mid] < target) {
// 右半部分继续搜索
left = mid + 1;
} else if(nums[mid] > target) {
// 左半部分继续搜索
right = mid - 1;
} else {
// 左右部分均有
// 则直接从当前位置,查找最左边的目标值
int first = mid;
while(first >= left && nums[first] == target) {
result[0] = first --;
}
// 则直接从当前位置,查找最右边的目标值
int last = mid;
while(last <= right && nums[last] == target) {
result[1] = last++;
}
break;
}
}
return result;
}
}

复杂度分析
时间复杂度:O(log(n))
空间复杂度:O(1)

参考资料

[1]

34. 在排序数组中查找元素的第一个和最后一个位置: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

原文始发于微信公众号(xiaogan的技术博客):34. 在排序数组中查找元素的第一个和最后一个位置