剑指offer-数字在排序数组中出现的次数

剑指offer-数字在排序数组中出现的次数

一、题目

统计一个数字在排序数组中出现的次数。例如输入排序数组{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肯定在数组的前半段,下一轮我们仍然需要在数组的前半段查找。

四、代码实现

>folded main.go
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
package main

import "fmt"

func numberCount(nums []int, target int) int {
// 二分查找初始化游标
left, right := 0, len(nums)-1
var mid int
for left < right {
mid = (left + right) / 2
// 中间元素与查找对象相等,继续在它两边查找
if nums[mid] == target {
// right在末尾,与中间元素不等,则往前面查找
for nums[mid] != nums[right] {
right--
}
// left在头部,与中间元素不等,则往后顺序查找
for nums[mid] != nums[left] {
left++
}
break
}
if nums[mid] > target {
// 中间元素比目标值大,则在数组的前半段去查找
right = mid - 1
} else {
// 中间元素比目标值大,则在数组的后半段去查找
left = mid + 1
}
}
if left < right {
return right-left+1
}
return -1
}

func main() {
test := []int{1, 2, 3, 3, 3, 3, 4, 5}
count := numberCount(test, 3)
fmt.Println("Count 3 in ", test, ": ", count)
}

// 输出如下:
Count 3 in [1 2 3 3 3 3 4 5] : 4

Process finished with exit code 0
评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...