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]
题目详解
思路
- 有序和数组这个两个字眼结合起来，肯定是要用到二分查找这一类；
- 首先就是找最左侧的下标，利用二分查找首先是找到有一个值是与目标值target是相等的，然后因为是找最左侧的下标，所以把right=mid-1来一直往左边去逼近最左侧的值；
- 至于找最右侧的下标就是，将left=mid+1,来去逼近最右侧的下标；
- 如果没有找到则说明不存在返回-1；
示例
这里举一个例子帮助大家理解，对于数组[1,2,4,4,4,4,4,5,6]，找4的最左下标。
- 对于这个数目来说，lfet,right,mid分别代表下标值首先left=0.right=8,所以mid=(0+8)/2 = 4；
- 由于target=4与nums[mid]相等，所以此时记录下来这个下标，也就是mid的值4，这个下标是可能的最左的4的下标所以要记录保存一下；
- 观察这个数组，可以知道，最左的4的下标是2，所以为了找到这个最左的下标，需要令right的值去等于mid-1;这样就把right这一边慢慢地往左靠，因为是找最左的嘛~，所以肯定是要缩小right的的值去逼近这个最左的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
