[关闭]
@liweiwei1419 2019-02-10T15:10:02.000000Z 字数 2548 阅读 925

《剑指 Offer》(第 2 版)第 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:写一个二分法,使用二分法找到大于等于 的第 个数的下标,再使用二分法找到大于等于 的第 个数的下标,二者之差即为所求。特别注意,这里是如何使用二分法的。

Python 代码:

  1. class Solution(object):
  2. # 返回大于等于 target 的第 1 个数
  3. def get_left(self, nums, target):
  4. # [2,3,4,5,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]
  6. if nums[0] == target:
  7. return 0
  8. l = 1
  9. r = len(nums)
  10. while l < r:
  11. mid = l + (r - l) // 2
  12. if nums[mid] < target:
  13. l = mid + 1
  14. else:
  15. assert nums[mid] >= target
  16. # 不能排除 mid
  17. r = mid
  18. return l
  19. def getNumberOfK(self, nums, k):
  20. """
  21. :type nums: list[int]
  22. :type k: int
  23. :rtype: int
  24. """
  25. size = len(nums)
  26. if size == 0:
  27. return 0
  28. return self.get_left(nums, k + 1) - self.get_left(nums, k)

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

Python 代码:

  1. class Solution(object):
  2. def getNumberOfK(self, nums, k):
  3. """
  4. :type nums: list[int]
  5. :type k: int
  6. :rtype: int
  7. """
  8. size = len(nums)
  9. if size == 0:
  10. return 0
  11. # 设置辅助函数,给一个 nums,一个 k,返回大于等于 k 的第一个数的索引
  12. return self.__helper(nums, k + 1) - self.__helper(nums, k)
  13. def __helper(self, nums, k):
  14. """
  15. 返回大于等于 k 的第一个数的索引
  16. :param nums:
  17. :param k:
  18. :return:
  19. """
  20. size = len(nums)
  21. if size == 0:
  22. return 0
  23. l = 0
  24. # 注意:这里一定要写 size
  25. r = size - 1
  26. while l < r:
  27. mid = l + (r - l) // 2
  28. if nums[mid] >= k:
  29. r = mid
  30. else:
  31. assert nums[mid] < k
  32. # [1,2,3,4,5]
  33. l = mid + 1
  34. # 因为 k 有可能不存在,所以不一定符合要求,所以一定要单独判断一下
  35. if nums[l] != k:
  36. if nums[size - 1] < k:
  37. return size
  38. elif nums[0] > k:
  39. return 0
  40. return l

C++ 代码:

  1. class Solution {
  2. public:
  3. int getNumberOfK(vector<int>& nums , int k) {
  4. if (nums.empty()) return 0;
  5. return helper(nums, k + 1) - helper(nums, k);
  6. }
  7. int helper(vector<int>& nums, int k){
  8. int l = 0, r = nums.size();
  9. while (l < r){
  10. int m = l + (r - l) / 2;
  11. if (nums[m] < k) l = m + 1;
  12. else r = m;
  13. }
  14. return l;
  15. }
  16. };

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

  1. # # 56、数字在排序数组中出现的次数
  2. # 统计一个数字在排序数组中出现的次数。
  3. #
  4. # 例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3,由于3在这个数组中出现了4次,因此输出4。
  5. class Solution(object):
  6. def getNumberOfK(self, nums, k):
  7. """
  8. :type nums: list[int]
  9. :type k: int
  10. :rtype: int
  11. """
  12. size = len(nums)
  13. if size == 0:
  14. return 0
  15. # 设置辅助函数,给一个 nums,一个 k,返回大于等于 k 的第一个数的索引
  16. k_right = self.__get_right_k(nums, k)
  17. k_left = self.__get_left_k(nums, k)
  18. if k_right == -1 or k_left == -1:
  19. return 0
  20. return k_right - k_left + 1
  21. def __get_right_k(self, nums, k):
  22. # 找到最右边的 index ,使得 nums[index] = k
  23. size = len(nums)
  24. if size == 0:
  25. return -1
  26. l = 0
  27. r = size - 1
  28. while l < r:
  29. mid = l + (r - l + 1) // 2
  30. if nums[mid] <= k:
  31. # [1,2,5,5,5,7]
  32. l = mid
  33. elif nums[mid] > k:
  34. r = mid - 1
  35. if nums[l] != k:
  36. return -1
  37. return l
  38. def __get_left_k(self, nums, k):
  39. # 找到最左边的 index ,使得 nums[index] = k
  40. size = len(nums)
  41. if size == 0:
  42. return -1
  43. l = 0
  44. r = size - 1
  45. while l < r:
  46. mid = l + (r - l) // 2
  47. if nums[mid] >= k:
  48. r = mid
  49. else:
  50. assert nums[mid] < k
  51. l = mid + 1
  52. if nums[l] != k:
  53. return -1
  54. return l
  55. if __name__ == '__main__':
  56. nums = [2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10]
  57. k = 5
  58. solution = Solution()
  59. # result = solution.get_left(nums, 5, )
  60. # print(result)
  61. result = solution.getNumberOfK(nums, k)
  62. print(result)

(本节完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注