剑指Offer面试题38（Java版）：数字在排序数组中出现的次数

爱被打了一巴掌 2022-07-16 04:51 116阅读 0赞

题目：统计一个数字在排序数组中出现的次数。例如输入排序数组为

\{1,2,3,3,,3,3,4,5\}和数字3，由于3在这个数组中出现了4次，因此输出4

既然输入的数组是排序的，那么我们很自然的想到利用二分查找算法。在题目给出的例子中，我们可以先用二分查找算法找到第一个3.由于3可能出现多次，因此我们找到的3的左右两遍可能都是3，于是我们在找到3的左右两边顺序扫描，分别找出第一个3和最后一个3.因为要查找的数字在长度为n的数组中可能很出现O(n)次，所以顺序扫描的时间复杂度为O(n)。因此这种算法的效率和直接从头到尾顺序扫描整个数组统计3出现的次数的方法是一样的。显然，面试官是不会满意这种算法，它会提示我们还有更快的算法。

接下来我们思考如何更好的利用二分查找算法。假设我们统计数字k在排序数组中出现的次数。在前面的算法的时间主要消耗在如何确定重复出现的第一个k和最后一个k的位置上，有没有可以利用的二分查找算法直接找到第一个k和最后一个k。

我们先分析如何利用二分查找在数组中找到第一个k，二分查找算法总是先拿数组的中间的数字和k做比较。如果中间的数字比k大，那么k只能出现在数组的前半段，下一轮我们旨在数组的前半段查找就可以了。如果中间的数字比k小，那么k只能出现在数组的后半段，下一轮我们只在数组的后半段查找就可以了。如果中间的数字和k相等呢？我们先判断这个数字是不是第一个k。如果位于中间数字的前面一个数字不是k，此时中间的数字刚好就是第一个k。如果中间的数字的前面一个数字也是k，也就是说第一个k肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找。

同理我们利用上面的思路找到最后一个k。

找到第一个k和最后一个k后就可以知道k出现的次数了，

实现代码如下：

**\[java\]**  [view plain][]   [copy][view plain]

1.  /\*\* 
2.   \* 统计一个数字在排序数组中出现的次数。 
3.   \* 例如输入排序数组｛1，2，3，3，3，3，4，5｝和数字3，由于3在这个数组中出现了4次，因此输出4 
4.   \*/  
5.  **package** swordForOffer;  
6.    
7.  /\*\* 
8.   \* @author JInShuangQi 
9.   \* 
10.  \* 2015年8月9日 
11.  \*/  
12. **public** **class** E38NumberOfK \{  
13.       
14.     **private** **int** getFirstK(**int**\[\] arr,**int** k,**int** left,**int** right)\{  
15.         **if**(left > right)  
16.             **return** -1;  
17.         **int** middleIndex = (left+right)/2;  
18.         **int** middleData = arr\[middleIndex\];  
19.         **if**(middleData == k)\{  
20.             **if**((middleIndex >0 && arr\[middleIndex -1\]!=k)|| middleIndex == 0)  
21.                 **return** middleIndex;  
22.             **else**  
23.                 right = middleIndex -1;  
24.         \}  
25.         **else** **if**(middleData > k)  
26.             right = middleIndex -1;  
27.         **else**  
28.             left = middleIndex +1;  
29.         **return** getFirstK(arr,k,left,right);  
30.     \}  
31.     **private** **int** getLastK(**int**\[\] arr,**int** k,**int** left,**int** right)\{  
32.         **if**(left > right)  
33.             **return** -1;  
34.         **int** middleIndex = (left + right)/2;  
35.         **int** middleData = arr\[middleIndex\];  
36.         **if**(middleData == k)\{  
37.             **if**((middleIndex <arr.length -1 && arr\[middleIndex+1\]!=k) || middleIndex ==arr.length-1)  
38.                 **return** middleIndex;  
39.             **else**  
40.                 left = middleIndex+1;  
41.         \}  
42.         **else** **if**(middleData <k)\{  
43.             left = middleIndex +1;  
44.         \}**else**  
45.             right = middleIndex -1;  
46.         **return** getLastK(arr,k,left,right);  
47.     \}  
48.     **public** **int** getNumberOfK(**int**\[\] arr,**int** k)\{  
49.         **int** number = 0;  
50.         **if**(arr.length >0)\{  
51.             **int** first = getFirstK(arr,k,0,arr.length-1);  
52.             **int** last = getLastK(arr,k,0,arr.length -1);  
53.             **if**(first >-1 && last >-1)  
54.                 number =last-first+1;  
55.         \}  
56.         **return** number;  
57.     \}  
58.     **public** **static** **void** main(String\[\] args)\{  
59.         **int**\[\] arr= \{ 1,2,3,3,3,3,4,5\};  
60.         E38NumberOfK test = **new** E38NumberOfK();  
61.         System.out.println(test.getNumberOfK(arr, 3));  
62.     \}  
63. \}

在上述代码中，getFirstK和getLastK都是利用二分查找法在数组中进行查找一个合乎要求的数字，它们的时间复杂度都是O(logn),因此getNumberOfK的总的时间复杂度也只有O（logn).

[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47381179#