栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

剑指 Offer 53 - I. 在排序数组中查找数字 I

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

剑指 Offer 53 - I. 在排序数组中查找数字 I

剑指 Offer 53 - I. 在排序数组中查找数字 I

题目描述:

统计一个数字在排序数组中出现的次数。

示例:

Input: nums = [5,7,7,8,8,10], target = 8
Output: 2

Input: nums = [5,7,7,8,8,10], target = 6
Output: 0

解题思路:

本题主要是考察二分法的边界条件的确定问题。题目中隐藏的信息是该数组是已经排序好的,而从示例可以看到,是按升序排序的,因此如果一个数字在该数组中重复出现,那么必定是连续的。想统计数组的出现次数只需要找到这个数字的左右边界,而二分法的一般结束循环的条件为,左指针索引大于右指针索引,因此只需要不断的缩小二分的范围,就可以找到左右边界。

算法代码:

class Solution {
    public int search(int[] nums, int target) {
    	// 首先初始化左右指针。
        int left = 0;
        int right = nums.length-1;
        // 确认target的右边界
        while(left <= right){
            int mid = (left + right) / 2; // 由于mid每次都要确定,因此写在循环之中,每次都重新定义。
            if(nums[mid]<=target) left = mid + 1;  // 这里要注意到这个等于号。等于号的意义在于如果找到了这个数,那么我就要将left往右移,直到mid不再等于该数,这时也就刚刚好跳出该数,也就确定了右边界。
            else right = mid - 1;
        }
        int rightIndex = left;  // 此时将left作为右边界。
        if(right > 0 && nums[right]!=target) return 0; // 如果存在target, 那么当left出target,right则应该刚好跳进该数。如果不相等,则不存在
        left = 0; right = nums.length - 1; //再次初始化指针
        // 确定
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid - 1; // 这时等号在右指针中,当相等时,右指针不断左移,直到找到左边界。
        }
        int leftIndex = right;
        return rightIndex - leftIndex - 1;
    }
}

小tips:

二分法的循环条件一般为左指针索引大于右指针索引,因此在循环中,一定要设定相应的条件使得左指针增加或右指针增加,不然就会陷入死循环之中。

但是也有例外,需要视实际情况而定。

如:剑指 Offer 11. 旋转数组的最小数字

如有错误,欢迎大家留言指出,大家一起进步

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/287499.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号