leetcode剑指 Offer 53 - I(在排序数组中查找数字 I)--Java语言实现

原创
07/11 22:39
阅读数 42

求:

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

 

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

 

限制:

0 <= 数组长度 <= 50000

 

注意:本题与主站 34 题相同(仅返回值不同):https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

 

题目链接: https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/

 

解:

1、二分搜索

因为是在有序数组中查找元素,所以首先想到使用二分搜索。但是这里我们需要对二分搜索进行简单改造,需要实现一个方法,能够查找到数组中target第一次出现的索引beginIndex和最后一次出现的索引endIndex。如果beginIndex==-1,说明数组中没有对应的元素,返回0,否则beginIndex和endIndex一定存在,返回endIndex-beginIndex+1。

时间复杂度:O(logN)

空间复杂度:O(1)

public int search(int[] nums, int target) {
    int start = 0, end = nums.length;
    int beginIndex = binarySearch(nums, target, 0, nums.length-1, true);
    if (beginIndex == -1) return 0;
    int endIndex = binarySearch(nums, target, beginIndex, nums.length-1, false);
    return endIndex - beginIndex + 1;
}

public int binarySearch(int[] nums, int target, int start, int end, boolean left) {
    int index = -1;
    while (start <= end) {
        int mid = (start + end) >> 1;
        if (nums[mid] == target) {
            index = mid;
            if (left) end = mid - 1;
            else start = mid + 1;
        } else if (nums[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return index;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部