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

  • 2019 年 10 月 4 日
  • 筆記

前言

今天刷的题目是:在排序数组中查找元素的第一个和最后一个位置,这道题目在最开始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:

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

示例 2:

输入: 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.

代码

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。

第一次代码优化

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。

第二次代码优化

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