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

题目信息

时间： 2019-07-04
题目链接：Leetcode
tag：二分查找哈希表
难易程度：简单
题目描述：

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

示例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;

    }

}

巴特西

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

题目信息

解题思路

代码

其他优秀解答

最新文章

热门文章