题目
剑指offer53-I：在排序数组中查找数字I
统计一个数字在排序数组中出现的次数。
示例1：
1
2
| 输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
|
示例2：
1
2
| 输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
|
代码
方案1：暴力破解
直接遍历数组，数组元素=target，次数+1。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int search(int[] nums, int target) {
int n=0;
for(int i=0;i<nums.length;i++){
if(nums[i]==target){
n++;
}
}
return n;
}
}
|
方案2：算法优化
采用二分法。
1、值为target的元素，在数组nums中，形成一个窗口。要想统计值为target元素的个数，只需找到窗口的右侧首元素索引right和左侧首元素索引left即可。值为target元素的个数 = right-(left+1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| public class Solution {
public static int search(int[] nums, int target) {
int i=0,j=nums.length-1;
while (i<=j){
int m=(i+j)/2;
if(nums[m]<=target){
i=m+1;
}else {
j=m-1;
}
}
int right = i;
if(j>=0 && nums[j]!=target) return 0;
i=0;j=nums.length-1;
while (i<=j){
int m=(i+j)/2;
if(nums[m]<target){
i=m+1;
}else {
j=m-1;
}
}
int left = j;
return right-(left+1);
}
}
|
2、换种思维方式，值为target的元素个数 = target窗口右侧首元素索引 - (target-1)窗口右侧首元素索引
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution {
public static int search(int[] nums, int target) {
return right(nums,target)-right(nums,target-1);
}
public static int right(int[] nums,int target){
int i=0,j=nums.length-1;
while (i<=j){
int m=(i+j)/2;
if(nums[m]<=target){
i=m+1;
}else {
j=m-1;
}
}
return i;
}
}
|
随笔
排序数组中的查找问题
首先想到用二分法来解决。
复杂度分析
方案1：
时间复杂度：O(n)，遍历为线性级别复杂度。
空间复杂度：O(1)，几个变量使用常数大小的额外空间。
方案2：
时间复杂度：O(logn)，二分法为对数级别复杂度。
空间复杂度：O(1)，几个变量使用常数大小的额外空间。
很显然，二分法更有优势。
