微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 53-1. 在排序数组中查找数字

剑指offer 53-1. 在排序数组中查找数字

题目描述

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

示例 1:

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

示例 2:

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

提示：

  • 0 <= nums.length <= 10^{5}
  • -10^{9} <= nums[i] <= 10^{9}
  • nums 是一个非递减数组
  • -10^{9} <= target <= 10^{9}

题解

(二分) O(logn)

在排序数组中快速找一个数可以用二分，题目要求找出连续的一段数 target 的个数，可以做两次二分，二分左端点和二分右端点。

算法步骤：

  1. 二分左端点的条件：找到第一个大于等于 target 的数的位置 left
  2. 二分结束，如果左端点对应的值不是 target，说明 target 不存在，直接返回 0，否则继续二分右端点
  3. 二分右端点的条件：找到最后一个个小于等于 target 的数的位置 right

最后返回出现的次数 right – left + 1。

时间复杂度

二分的时间复杂度为 O(logn)

空间复杂度

O(1)

C++ 代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return 0;
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        if (nums[l] != target) return 0;

        int left = l;
        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1ll >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }

        return r - left + 1;
    }
};

Java 代码

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        if (nums[l] != target) {
            return 0;
        }

        int left = l;
        l = 0;
        r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        return r - left + 1;
    }
}

Python 代码

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        l, r = 0, len(nums) - 1
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1

        if nums[l] != target:
            return 0

        left = l
        l, r = 0, len(nums) - 1
        while l < r:
            mid = l + (r - l + 1) // 2
            if nums[mid] <= target:
                l = mid
            else:
                r = mid - 1

        return r - left + 1

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer