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

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

作者: 周英杰Anita | 来源:发表于2020-02-25 16:36 被阅读0次

    题目描述:

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

    1、二分法先找到右边界;
        1、设定左右指针left = 0和right=len-1,找到中间数num[min]
        2、比较目标值与num[min]的大小,大于目标值则修改右指针right = mid - 1;
        3、小于目标值则修改左指针 left = mid + 1;
        4、等于目标值,则判断是否该指针是最后一个,或者是否下一个数比目标值大,如果都不是,如是,则ans[1] = mid;如否,则修改左指针left = mid + 1;
    2、二分法再找到左边界;
        1、设定左右指针left = 0和right=ans[1],找到中间数num[min]
        2、比较目标值与num[min]的大小,大于目标值则修改右指针right = mid - 1;
        3、小于目标值则修改左指针 left = mid + 1;
        4、等于目标值,则判断是否该指针是第一个,或者是否前一个数比目标值小,如是,则ans[0] = mid;如否,则修改左指针right = mid - 1;
    3、最终返回结果ans;
    

    Java解法:

    class Solution {
        public int[] searchRange(int[] nums, int target) {
            int len = nums.length;
            if(len ==0 || nums[0] > target || nums[len - 1] < target){
                return new int[]{-1, -1};
            }
            int left = 0;
            int right = len - 1;
            int[] ans = new int[]{-1, -1};
            while(left <= right)
            {
                int mid = (left + right) / 2;
                if (nums[mid] > target)
                {
                    right = mid - 1;
                }else if(nums[mid] < target)
                {
                    left = mid + 1;
                }else {
                    if (mid == len - 1 || nums[mid + 1] > target)
                    {
                        ans[1] = mid;
                        break;
                    }else
                    {
                        left = mid + 1;
                    }
                }
            }
            left = 0;
            right = ans[1];
            while(left <= right)
            {
                int mid = (left + right) / 2;
                if (nums[mid] > target)
                {
                    right = mid - 1;
                }else if(nums[mid] < target)
                {
                    left = mid + 1;
                }else {
                    if (mid == 0 || nums[mid - 1] < target)
                    {
                        ans[0] = mid;
                        break;
                    }else
                    {
                        right = mid - 1;
                    }
                }
            }
            return ans;
        }
    }
    

    python3解法:

    
    

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

    相关文章

      网友评论

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

          本文链接:https://www.haomeiwen.com/subject/ezotchtx.html