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

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

一、题目

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

二、思路

1、思路一

刚看题目,冒出的第一个思路,比较易懂先找到一个元素,从这个元素分别往左边和往右边遍历,找到左右边界即可。

这个这个时间复杂度为 log(n)+m,n为数组大小,m为target目标的个数 。

题目要求是 O(log n)级别。所以这个不太严谨。

2、思路二

分别用二分找到左边界和右边界,而不是用遍历查找。

既然要找到左右边界,那当num[mid] == target 的时候,左右指针的移动不能停,而要继续向左或者右移动。

三、代码

注意,当num[mid] == target相等的时候,num[mid] 元素应该被包括在搜索范围内。另外,while 循环的条件和数组的范围越界也需要注意。

public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        int[] res = {-1, -1};
        if (len == 0 || nums[len - 1] < target || nums[0] > target) {
            return res;
        }
        res[0] = searchLeft(nums, target);
        res[1] = searchRight(nums, target);
        return res;
    }

    private int searchLeft(int[] nums, int target) {
        int len = nums.length;
        int low = 0;
        int high = len == 0 ? 0 : len - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (nums[mid] >= target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        if (nums[low] == target) {
            return low;
        }
        return -1;
    }

    private int searchRight(int[] nums, int target) {
        int len = nums.length;
        int low = 0;
        int high = len == 0 ? 0 : len - 1;
        while (low + 1 < high) {
            int mid = (low + high) / 2;
            if (nums[mid] <= target) {
                //low 可以相等
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        if (nums[high] == target) {
            return high;
        }
        if (nums[low] == target) {
            return low;
        }
        return -1;
    }

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注