内容简介:注意本题难点排序数组中查找数字,性能最优。
题目信息
示例1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: 2
示例2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: 0
注意
1. 0 <= 数组长度 <= 50000
解题思路
本题难点
排序数组中查找数字,性能最优。
具体思路
排序数组中的搜索问题,首先想到 二分法 解决。
排序数组 nums 中的所有数字 target 形成一个窗口,记窗口的 左 / 右边界 索引分别为 left 和 right ,分别对应窗口左边 / 右边的首个元素。
统计数字 target 的出现次数,可转化为:使用二分法分别找到 左边界 left 和 右边界 right ,易得数字 target 的数量为 right−left−1 。
- 计算中点 m=(i+j)/2(向下取整)
- 若 nums[m]<target ,则 target 在闭区间 [m+1,j] 中,因此执行 i=m+1;
- 若 nums[m]>target ,则 target 在闭区间 [i,m−1] 中,因此执行 j=m−1;
-
若 nums[m]=target ,则右边界 right 在闭区间 [m+1,j] 中;左边界 left 在闭区间 [i,m−1] 中。
- 若查找 右边界 right ,则执行 i=m+1 ;(跳出时 i指向右边界)
- 若查找 左边界 left ,则执行 j=m−1 ;(跳出时 j指向左边界)
提示:查找完右边界后,可用 nums[j]=j 判断数组中是否包含 target ,若不包含则直接提前返回 0 ,无需后续查找左边界。查找完右边界后,左边界 left一定在闭区间 [0,j] 中,因此直接从此区间开始二分查找即可。
代码
class Solution { public int search(int[] nums, int target) { // 搜索右边界 right int i = 0, j = nums.length - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] <= target) i = m + 1; else j = m - 1; } int right = i; // 若数组中无 target ,则提前返回 if(j >= 0 && nums[j] != target) return 0; // 搜索左边界 right i = 0; while(i <= j) { int m = (i + j) / 2; if(nums[m] < target) i = m + 1; else j = m - 1; } int left = j; return right - left - 1; } }
复杂度分析:
- 时间复杂度 O(logN) : 二分法为对数级别复杂度。
- 空间复杂度 O(1) :几个变量使用常数大小的额外空间。
其他优秀解答
解题思路
直接遍历排序数组,计数。
代码
class Solution { public int search(int[] nums, int target) { int count = 0; for(int num : nums){ if(num == target){ count++; } } return count; } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- JavaScript数组-排序算法
- 数组的去重和排序
- javascript 数组排序(sort,冒泡)
- Go 寻找数组中最小的 k 个数:全部排序和部分排序
- JS骚操作之数组快速排序
- 数组排序并插入值算法(JavaScript)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。