网站建设 后端开发软件,昆明网站建设教学视频,网站优化公司排名深圳,西安稳定的seo【问题描述】[中等]
统计一个数字在排序数组中出现的次数。
示例 1:输入: nums [5,7,7,8,8,10], target 8
输出: 2
示例 2:输入: nums [5,7,7,8,8,10], target 6
输出: 0【解答思路】
1. 暴力法/遍历
时间复杂度#xff1a;O(N) 空间复杂度#xff1a;O(1) public int…【问题描述】[中等]
统计一个数字在排序数组中出现的次数。
示例 1:输入: nums [5,7,7,8,8,10], target 8
输出: 2
示例 2:输入: nums [5,7,7,8,8,10], target 6
输出: 0
【解答思路】
1. 暴力法/遍历
时间复杂度O(N) 空间复杂度O(1) public int search(int[] nums, int target) {int count 0;for(int num : nums){if(num target){count;}}return count;}2. 二分法
有序数组 分别找到 taret 的左右边界 right - left 1 时间复杂度O(logN) 空间复杂度O(1)
public class Solution {public int search(int[] nums, int target) {int len nums.length;if (len 0) {return 0;}int firstPosition findFirstPosition(nums, target);if (firstPosition -1) {return 0;}int lastPosition findLastPosition(nums, target);return lastPosition - firstPosition 1;}private int findFirstPosition(int[] nums, int target) {int len nums.length;int left 0;int right len - 1;while (left right) {int mid left (right - left) / 2;// 注意这样写可以从左边收缩待搜索区间的范围进而找到第一次出现的位置if (nums[mid] target) {// mid 以及 mid 左边都不是下一轮搜索区间在 [mid 1, right]left mid 1;} else {right mid;}}if (nums[left] target) {return left;}return -1;}private int findLastPosition(int[] nums, int target) {int len nums.length;int left 0;int right len - 1;while (left right) {int mid left (right - left 1) / 2;// 注意这样写可以从右边收缩待搜索区间的范围进而找到最后一次出现的位置if (nums[mid] target) {// mid 以及 mid 右边都不是下一轮搜索区间在 [left, mid - 1]right mid - 1;} else {left mid;}}return left;}
}
【总结】
1.二分查找思路 2.排除法思考二分法 1、确定搜索区间初始化时候的左右边界有时需要关注一下边界值。在初始化时有时把搜索区间设置大一点没有关系但是如果恰好把边界值排除在外再怎么搜索都得不到结果。
2、无条件写上 while (left right) 表示退出循环的条件是 left right对于返回左右边界就不用思考了因此此时它们的值相等
3、先写下取整的中间数取法然后从如何把 mid 排除掉的角度思考 if 和 else 语句应该怎样写。
这里建议写两个注释。
一般而言我都会把**“什么时候不是目标元素”**作为注释写在代码中提醒自己要判断正确这一步判断非常关键直接影响到后面的代码逻辑。然后接着思考 mid 不是解的情况下mid 的左右两边可能存在解把下一轮搜索的区间范围作为注释写进代码里进而在确定下一轮搜索区间边界的收缩行为时不容易出错。
if 有把握写对的情况下else 就是 if 的反面可以不用思考直接写出来。
** 说明这种思考方式就正正好把待搜索区间从逻辑上分成两个区间一个区间不可能存在目标元素进而在另一个区间里继续搜索更符合“二分”的语义。**
4、根据 if else 里面写的情况看看是否需要修改中间数下取整的行为。 上面已经说了只有看到 left mid 的时候才需要调整成为上取整记住这一点即可我因为刚开始不理解这种写法遇到很多次死循环现在已经牢记在心了。
5、退出循环的时候一定有 left right 成立。有些时候可以直接返回 left 或者 right由于它们相等后面都省略括弧或者与 left 相关的数值有些时候还须要再做一次判断判断 left 与 right 是否是我们需要查找的元素这一步叫“后处理”。
// 有可能区间内不存在目标元素因此还需做一次判断if (nums[left] target) {return left;}return -1;public int searchInsert(int[] nums, int target) {int len nums.length;if (len 0) {return 0;}int left 0;// 因为有可能数组的最后一个元素的位置的下一个是我们要找的故右边界是 lenint right len;while (left right) {int mid (left right) 1;// 小于 target 的元素一定不是解if (nums[mid] target) {// 下一轮搜索的区间是 [mid 1, right]left mid 1;} else {right mid;}}return left;} 转载链接https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/er-fen-cha-zhao-fa-zhao-dao-di-yi-ci-chu-xian-de-w/
