前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode34-在排序数组中查找元素的第一个和最后一个位置

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

作者头像
乔戈里
发布2019-09-17 11:06:06
2.6K0
发布2019-09-17 11:06:06
举报
文章被收录于专栏:Java那些事

前言

今天刷的题目是:在排序数组中查找元素的第一个和最后一个位置,这道题目在最开始AC以后,然后做了两步的优化操作,供大家参考。

题目

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

分类(tag):二分查找这一类

英文链接:https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

中文链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

题目详述

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

你的算法时间复杂度必须是 O(log n) 级别。

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

示例 1:

代码语言:javascript
复制
输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4]

示例 2:

代码语言:javascript
复制
输入: nums = [5,7,7,8,8,10], target = 6输出: [-1,-1]

题目详解

思路

  1. 有序和数组这个两个字眼结合起来,肯定是要用到二分查找这一类;
  2. 首先就是找最左侧的下标,利用二分查找首先是找到有一个值是与目标值target是相等的,然后因为是找最左侧的下标,所以把right=mid-1来一直往左边去逼近最左侧的值;
  3. 至于找最右侧的下标就是,将left=mid+1,来去逼近最右侧的下标;
  4. 如果没有找到则说明不存在返回-1;

示例

这里举一个例子帮助大家理解,对于数组[1,2,4,4,4,4,4,5,6],找4的最左下标。

  1. 对于这个数目来说,lfet,right,mid分别代表下标值首先left=0.right=8,所以mid=(0+8)/2 = 4;
  2. 由于target=4与nums[mid]相等,所以此时记录下来这个下标,也就是mid的值4,这个下标是可能的最左的4的下标所以要记录保存一下;
  3. 观察这个数组,可以知道,最左的4的下标是2,所以为了找到这个最左的下标,需要令right的值去等于mid-1;这样就把right这一边慢慢地往左靠,因为是找最左的嘛~,所以肯定是要缩小right的的值去逼近这个最左的4,直到找到这个最左的4为止~;
  4. 找最右边的4的思路也是一样的哦,就是令left=mid+1去逼近最右边的这个4.

代码

代码语言:javascript
复制
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int [] result = {-1,-1};
        result[0] = findLeftIndex(nums,target);
        result[1] = findRightIndex(nums,0,target);
        return result;
    }
    public int findLeftIndex(int [] nums,int target)
    {
        int left = 0;
        int right = nums.length - 1;
        int leftIndex = -1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else{
                leftIndex = mid;
                right = mid - 1;
            }
        }
        return leftIndex;
    }
    public int findRightIndex(int [] nums,int left,int target)
    {

        int right = nums.length - 1;
        int rightIndex = -1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else{
                rightIndex = mid;
                left = mid + 1;
            }
        }
        return rightIndex;
    }
}

代码就是一个二分查找,前面已经讲过了二分查找,(二分查找:RNG输了,但我们不能输)这里不再继续讲,讲一下代码23行到24行,leftIndex就是我之前说的保存这个已经找的的下标,24行就是因为是找最最左边的下标,所以把right的值赋值为mid-1,以此来往最左边出现的target来逼近。44行-45行也是同理,不再赘述了。这个是最初的版本,然后我写完了以后,又进行了两次优化,最终时间缩短了2ms。

第一次代码优化

代码语言:javascript
复制
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int [] result = {-1,-1};
        result[0] = findLeftIndex(nums,target);
        if(result[0] != -1)
            result[1] = findRightIndex(nums,0,target);
        return result;
    }
    public int findLeftIndex(int [] nums,int target)
    {
        int left = 0;
        int right = nums.length - 1;
        int leftIndex = -1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else{
                leftIndex = mid;
                right = mid - 1;
            }
        }
        return leftIndex;
    }
    public int findRightIndex(int [] nums,int left,int target)
    {

        int right = nums.length - 1;
        int rightIndex = -1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else{
                rightIndex = mid;
                left = mid + 1;
            }
        }
        return rightIndex;
    }
}

可以看到第5行,先判断了最左边的下标是不是-1,如果不是-1,那说明需要继续找最右边的下标,如果是-1的话,那么说明数组中没有target的值,所以我们也不必在去找最右边的下标了,因为已经找过了,不存在的,还费这事干嘛,最终这样优化完速度快了1ms。

第二次代码优化

代码语言:javascript
复制
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int [] result = {-1,-1};
        result[0] = findLeftIndex(nums,target);
        if(result[0] != -1)
            result[1] = findRightIndex(nums,result[0],target);
        return result;
    }
    public int findLeftIndex(int [] nums,int target)
    {
        int left = 0;
        int right = nums.length - 1;
        int leftIndex = -1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else{
                leftIndex = mid;
                right = mid - 1;
            }
        }
        return leftIndex;
    }
    public int findRightIndex(int [] nums,int left,int target)
    {

        int right = nums.length - 1;
        int rightIndex = -1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else{
                rightIndex = mid;
                left = mid + 1;
            }
        }
        return rightIndex;
    }
}

可以看到第6行中,进行了代码优化,把result[0],作为参数传入了找最右边的方法中。因为这样的话,可以缩短二分查找的范围,找的范围小了,所以肯定快了,最终又快了1ms~

结果展示

无图无真相~

结束语

虽然简单,但是要尽量写出最优解~

END

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-10-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员乔戈里 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档