leetcode 剑指 Offer 53

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

题目描述

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

示例 1:

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

示例 2:

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

限制：

0 <= 数组长度 <= 50000

思路一：

先使用二分法查找数字的下标，如果找到了在这个下标的前后分别计数累加，否则直接返回0

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3         
 4         // 二分法查找数字的下标
 5         int index = binaryFind(nums, target);
 6         int cnt = 0;
 7         // 如果找到了在这个下标的前后分别计数累加
 8         if(index != -1){
 9             cnt = 1;
10             int j = index + 1;  // 分别向左和向右统计与target相等的元素个数
11             int len = nums.length;
12             while(j < len && nums[j] == target){
13                 cnt++;
14                 j++;
15             }
16             j = index - 1;
17             while(j >= 0 && nums[j] == target){
18                 cnt++;
19                 j--;
20             }
21         }
22         return cnt;
23     }
24 
25     public int binaryFind(int[] nums, int target){
26         int left = 0, right = nums.length - 1;
27         int mid = 0;
28         while(left <= right){
29             mid = (left + right) / 2;
30             if(target < nums[mid]){
31                 right = mid - 1;
32             }else if(target > nums[mid]){
33                 left = mid + 1;
34             }else{
35                 return mid;
36             }
37         }
38         return -1;
39     }
40 
41 }

leetcode运行时间为0ms, 空间为42MB

复杂度分析：

时间复杂度：二分查找的时间为O(logn), 第二次往前后查找给定数字的查找次数是不确定的，最坏是O(n),所以时间复杂度为O(n)

空间复杂度：O(1)

思路二：

查找 taget 在数组的左右边界，左右边界做差再减一即为出现的次数，比如下标 4、5 元素都是8，那我们通过二分法找到的上下边界是3 和6，所以8的个数应该是 6-3-1 = 2

if(target >= nums[mid])则 left = mid + 1, 可以找到第一个大于target元素的元素下标(最终left所在位置)，

同理 if(target <= num[mid]) 则 right = mid - 1, 那么可以找到第一个小于target 元素的元素下标(最终right所在下标）

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3 
 4         // 二分法查找数字的左右边界下标
 5         int left = 0, right = nums.length - 1;
 6         int mid = 0;
 7         // 二分法查找数值的右边界下标
 8         while(left <= right){
 9             mid = (left + right) / 2;
10             if(target >= nums[mid]){
11                 left = mid + 1;
12             }else{
13                 right = mid - 1;
14             }
15         }
16         int rightBorder = left;
17 
18         left = 0;
19         // 二分法查找target的左边界下标
20         while(left <= right){
21             mid = (left + right) / 2;
22             if(target <= nums[mid]){
23                 right = mid - 1;
24             }else{
25                 left = mid + 1;
26             }
27         }
28 
29         int leftBorder = right;
30         return rightBorder - leftBorder - 1;
31     }
32 }

leetcode运行时间为0ms, 空间为41.9MB

复杂度分析：

时间复杂度：二分查找为对数级别的复杂度，所以时间复杂度为O(logn)

空间复杂度：O(1)

思路三：

对思路二的改进, 查找左边界可以用查找（target - 1）的右边界来代替，这样思路二种二分法的两段代码可以抽取出来成一段代码。可以看到，代码简化了很多。

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3 
 4         // 用target的右边界减去(target-1)的右边界即可
 5         return binaryFindRightBorder(nums, target) - binaryFindRightBorder(nums, target-1);
 6     }
 7 
 8     public int binaryFindRightBorder(int[] nums, int target){
 9         // 二分法查找数字的左右边界下标
10         int left = 0, right = nums.length - 1;
11         int mid = 0;
12         // 二分法查找数值的右边界下标
13         while(left <= right){
14             mid = (left + right) / 2;
15             if(target >= nums[mid]){
16                 left = mid + 1;
17             }else{
18                 right = mid - 1;
19             }
20         }
21         return left;
22     }
23 }

leetcode运行时间为0ms, 空间为41.6MB

复杂度分析：

时间复杂度：二分查找为对数级别的复杂度，所以时间复杂度为O(logn)

空间复杂度：O(1)

思路二和思路三均参考自：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/