leetcode 劍指 Offer 53 - I. 在排序數組中查找數字 I

劍指 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)

思路三：

對思路二的改進, 查找左邊界可以用查找（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