提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

【力扣刷题】34. 在排序数组中查找元素的第一个和最后一个位置

数组排序 一个 查找 元素 位置 最后 第一个
2023-06-13 09:14:29 时间

一、题目描述

来源:力扣（LeetCode） 整数数组 nums 按升序排列，数组中的值 互不相同 。

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？   示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

二、思路分析

使用双指针，一个从左遍历，一个从右遍历，找到的第一个就是元素的第一个位置和最后一个位置

三、代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1,-1};

        if(nums.length == 0){
            return res;
        }
        int left = 0;
        int right = nums.length -1;
        for (int i = 0; i < nums.length; i++) {
            if(nums[left] == target &amp;&amp; res[0] == -1){
                res[0] = left;
            }
            if(nums[right] == target &amp;&amp; res[1] == -1){
                res[1] = right;
            }
            left++;
            right--;
        }
        return res;
    }
}

四、运行结果

总结

这道题后续想了想，可能加上二分查找，查找到最接近范围的数组可能效率更快，待考证,先上个思路看的明白的

相关文章