1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 53 题] “在排序数组中查找数字”做题记录

[剑指 Offer 第 2 版第 53 题] “在排序数组中查找数字”做题记录

第 53 题:数字在排序数组中出现的次数 (二分法典型问题)

传送门:数字在排序数组中出现的次数

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

例如输入排序数组 [1, 2, 3, 3, 3, 3, 4, 5] 和数字 3 ,由于 3 在这个数组中出现了 4 次,因此输出4。

样例:

输入:[1, 2, 3, 3, 3, 3, 4, 5] , 3

输出:4

参考资料:《剑指 Offer》(第 2 版)第 53 题:数字在排序数组中出现的次数

思路1:写一个二分法,使用二分法找到大于等于 k 的第 1 个数的下标,再使用二分法找到大于等于 k+1 的第 1 个数的下标,二者之差即为所求。特别注意,这里是如何使用二分法的。

Python 代码:

  class Solution(object):

        # 返回大于等于 target 的第 1 个数
        def get_left(self, nums, target):
            # [2,3,4,5,5,5,5,5,5,5]
            # [1,1,1,1,1,1,1,1,1,2,3,4,5,5,5,5,5,5,5]
            if nums[0] == target:
                return 0
            l = 1
            r = len(nums)
            while l < r:
                mid = l + (r - l) // 2
                if nums[mid] < target:
                    l = mid + 1
                else:
                    assert nums[mid] >= target
                    # 不能排除 mid
                    r = mid
            return l

        def getNumberOfK(self, nums, k):
            """
            :type nums: list[int]
            :type k: int
            :rtype: int
            """
            size = len(nums)
            if size == 0:
                return 0

            return self.get_left(nums, k + 1) - self.get_left(nums, k)

严格按照二分法模板的话,代码要这样写:

Python 代码:

  class Solution(object):

        def getNumberOfK(self, nums, k):
            """
            :type nums: list[int]
            :type k: int
            :rtype: int
            """
            size = len(nums)
            if size == 0:
                return 0

            # 设置辅助函数,给一个 nums,一个 k,返回大于等于 k 的第一个数的索引
            return self.__helper(nums, k + 1) - self.__helper(nums, k)

        def __helper(self, nums, k):
            """
            返回大于等于 k 的第一个数的索引
            :param nums:
            :param k:
            :return:
            """
            size = len(nums)
            if size == 0:
                return 0

            l = 0
            # 注意:这里一定要写 size
            r = size - 1
            while l < r:
                mid = l + (r - l) // 2
                if nums[mid] >= k:
                    r = mid
                else:
                    assert nums[mid] < k
                    # [1,2,3,4,5]
                    l = mid + 1
            # 因为 k 有可能不存在,所以不一定符合要求,所以一定要单独判断一下
            if nums[l] != k:
                if nums[size - 1] < k:
                    return size
                elif nums[0] > k:
                    return 0
            return l

C++ 代码:

  class Solution {
    public:
        int getNumberOfK(vector<int>& nums , int k) {
            if (nums.empty()) return 0;
            return helper(nums, k + 1) - helper(nums, k);
        }

        int helper(vector<int>& nums, int k){
            int l = 0, r = nums.size();
            while (l < r){
                int m = l + (r - l) / 2;
                if (nums[m] < k) l = m + 1;
                else r = m;
            }
            return l;
        }
    };

思路2:写两个二分法,一个数出现的次数,一个数最右边的索引 – 一个数最左边的索引 + 1。

  # # 56、数字在排序数组中出现的次数
    # 统计一个数字在排序数组中出现的次数。
    #
    # 例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3,由于3在这个数组中出现了4次,因此输出4。


    class Solution(object):

        def getNumberOfK(self, nums, k):
            """
            :type nums: list[int]
            :type k: int
            :rtype: int
            """
            size = len(nums)
            if size == 0:
                return 0

            # 设置辅助函数,给一个 nums,一个 k,返回大于等于 k 的第一个数的索引

            k_right = self.__get_right_k(nums, k)
            k_left = self.__get_left_k(nums, k)

            if k_right == -1 or k_left == -1:
                return 0

            return k_right - k_left + 1

        def __get_right_k(self, nums, k):
            # 找到最右边的 index ,使得 nums[index] = k
            size = len(nums)
            if size == 0:
                return -1
            l = 0
            r = size - 1
            while l < r:
                mid = l + (r - l + 1) // 2
                if nums[mid] <= k:
                    # [1,2,5,5,5,7]
                    l = mid
                elif nums[mid] > k:
                    r = mid - 1
            if nums[l] != k:
                return -1
            return l

        def __get_left_k(self, nums, k):
            # 找到最左边的 index ,使得 nums[index] = k
            size = len(nums)
            if size == 0:
                return -1
            l = 0
            r = size - 1
            while l < r:
                mid = l + (r - l) // 2
                if nums[mid] >= k:
                    r = mid
                else:
                    assert nums[mid] < k
                    l = mid + 1
            if nums[l] != k:
                return -1
            return l


    if __name__ == '__main__':
        nums = [2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10]
        k = 5
        solution = Solution()
        # result = solution.get_left(nums, 5, )
        # print(result)

        result = solution.getNumberOfK(nums, k)
        print(result)

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 53 题] “在排序数组中查找数字”做题记录

链接:https://www.javajike.com/article/3298.html

« [剑指 Offer 第 2 版第 52 题] “两个链表的第一个公共结点”做题记录
[剑指 Offer 第 2 版第 54 题] “二叉搜索树的第k个结点”做题记录»

相关推荐

QR code