剑指Offer:数字在排序数组中出现的次数

题目

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

分析

由于数组是有序的,我们当然可以直接遍历一边数组,但是作为一个ACMer,你们能忍受这样的效率吗?

我不能,所以我选择下面这种方法;

由于数组有序,我们很快就能想到二分查找。以上面的数组为例,我们用两边二分查找分别找到最左边的3和最右边的3,然后他们之间的距离就是最后要输出的值。

接下来我们来分析以下如何用二分查找来找到数组中的第一个k。二分查找总是先拿数组中间的数字和k作比较。如果中间的数字比k大,那么k只可能出现在数组的前半段,之后我们只在数组的前半段查找就可以了。反之,同样。但是如果中间的数字和k相同,我们先判断它是否是第一个k,如果不是我们继续在数组的前半段查找。

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
40
41
42
43
44
45
46
47
48
49
public class Solution {
public static int GetFirstK(int[] array, int lenght, int begin, int end, int k) {
if (end < begin)
return -1;
int midIndex = (end+begin)/2;
int midData = array[midIndex];
if (midData == k) {
if ((midIndex > 0 && array[midIndex-1]!=k) || midIndex == 0)
return midIndex;
else
end = midIndex-1;
} else if (midData < k) {
begin = midIndex+1;
} else {
end = midIndex-1;
}
return GetFirstK(array, lenght, begin, end, k);
}

public static int GetLastK(int[] array, int lenght, int begin, int end, int k) {
if (end < begin)
return -1;
int midIndex = (end+begin)/2;
int midData = array[midIndex];
if (midData == k) {
if ((midIndex < lenght-1 && array[midIndex+1]!=k) || midIndex == lenght-1)
return midIndex;
else
begin = midIndex+1;
} else if (midData < k) {
begin = midIndex+1;
} else {
end = midIndex-1;
}
return GetLastK(array, lenght, begin, end, k);
}

public static int GetNumberOfK(int [] array , int k) {
int lenght = array.length;
int result = 0;
if (array != null && lenght != 0) {
int first = GetFirstK(array, lenght, 0, lenght-1, k);
int last = GetLastK(array, lenght, 0, lenght-1, k);
if (first != -1 && last != -1)
result = last-first+1;
}
return result;
}
}
有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%