【剑指Offer】53.1在排序数组中查找数字 I

时间:2020-8-30 作者:admin


NowCoder

题目描述

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

Input:
nums = 1, 2, 3, 3, 3, 3, 4, 6
K = 3

Output:
4

解题思路

class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0)
            return 0;
        
        // 二分 
        int star = binarySearch(nums, target), end = binarySearch(nums, target+1);
        // 考虑target和target+1,将两个起始位置相减。注意end-star+(1|0)
        return end - star + (nums[end] == target ? 1 : 0);
    }

    // 二分
    private static int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        
        while(l < r) {
            int mid = l + (r - l) / 2;
            // [l mid] [mid+1, r]
            if(nums[mid] < target)
                l = mid + 1;
            else
                r = mid;
        }
        return l;        
    }
}
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。