【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）
53 数字在排序数组中出现的次数
题目描述
统计一个数字在排序数组中出现的次数。
//方法一：顺序扫描，统计出现的次数，O(n)
/*
方法二：由于是有序数组，可以用二分查找
用
stl
中函数
lower_bound
和
upper_bound
O(logn) O(1)
*/
class
Solution
{
public
:
int
GetNumberOfK
(
vector
<
int
>&
data
,
int
k
)
{
if
(
data
.
empty
())
return
0
;
vector
<
int
>::
iterator first
=
lower_bound
(
data
.
begin
(),
data
.
end
(),
k
);
//
返回第一个大于等于
k
的位置
vector
<
int
>::
iterator last
=
upper_bound
(
data
.
begin
(),
data
.
end
(),
k
);
//
返回第一个大于
k
的位置
return
last
-
first
;
}
};
/*
方法：自己实现
lower_bound
和
upper_bound
O(logn) O(1)
*/
class
Solution
{
public
:
int
GetNumberOfK
(
vector
<
int
>&
data
,
int
k
)
{
if
(
data
.
empty
())
return
0
;
int
first
=
my_lower_bound
(
data
,
k
);
//
返回第一个大于等于
k
的位置
int
last
=
my_upper_bound
(
data
,
k
);
//
返回第一个大于
k
的位置
return
last
-
first
;
}
private
:
int
my_lower_bound
(
vector
<
int
>&
a
,
int
target
)
{
int left = 0, right = a.size();
//
与
stl
中喜欢把
end
指向末尾后一个元素的做法类似
while
(
left
<
right
)
{
int
mid
=
left
+
(
right
-
left
)
/
2
;
if
(
a
[
mid
]
<
target
)
left
=
mid
+
1
;
else
//
没有单独考虑等于的情况
right
=
mid
;
}
return
right
;
}
int
my_upper_bound
(
vector
<
int
>&
a
,
int
target
)
{
int
left
=
0
,
right
=
a
.
size
();
//
与
stl
中喜欢把
end
指向末尾后一个元素的做法类似
while
(
left
<
right
)
{
int
mid
=
left
+
(
right
-
left
)
/
2
;
if
(
a
[
mid
]
<=
target
)
left
=
mid
+
1
;
else
right
=
mid
;
}
return
right
;
}
};
//方法二：由于是有序的，可以用二分查找，找到该数第一次出现的位置和最后一次出现的位置，计算次数即可
//O(logn)
class
Solution
{
public
:
int
GetNumberOfK
(
vector
<
int
>&
data
,
int
k
)
{
if
(
data
.
empty
())
return
0
;
int
first
=
getFirst
(
data
,
k
);
int
last
=
getLast
(
data
,
k
);
if(first != -1 && last != -1) return last - first + 1;
else
return
0
; //如果找不到就返回0
}
private
:
int getFirst(vector<int>& a, int k)
{
int
left
=
0
;
int
right
=
a
.
size
()
-
1
;
int
mid
;
while
(
left
<=
right
)
{
mid
= (left+right) / 2;
if
(
a
[
mid
]
<
k
)
left
=
mid
+
1
;
else
if
(
a
[
mid
]
>
k
)
right
=
mid
-
1
;
else if(mid-1 >= 0 && a[mid-1] == k)
//当前数等于k,前一个数也等于k时，继续在左半区间查找
right
=
mid
-
1
;
else
//当前数等于k,前一个数不等于k或者为开头时，返回mid
return
mid
;
}
return
-
1
;
//找不到时返回-1
}
int getLast(vector<int>& a, int k)
{
int
left
=
0
;
int
right
=
a
.
size
()
-
1
;
int
mid
;
while
(
left
<=
right
)
{
mid
= (left+right) / 2;
if
(
a
[
mid
]
<
k
)
left
=
mid
+
1
;
else
if
(
a
[
mid
]
>
k
)
right
=
mid
-
1
;
else if(mid+1 < a.size() && a[mid+1] == k)
//当前数等于k,后一个数也等于k时，继续在右半区间查找
left
=
mid
+
1
;
else
//当前数等于k,后一个数不等于k或者后一个数为末尾时，返回mid
return
mid
;
}
return
-
1
;
//找不到时返回-1
}
};
//回顾普通的二分查找
int binarysearch(vector<int>& a, int k)
{
int
left
=
0
;
int
right
=
a
.
size
()
-
1
;
int
mid
;
while
(
left
<=
right
)
{
mid
=
(
left
+
right
)
/
2
;
if
(
a
[
mid
]
<
k
)
//k较a[mid]大时，在右半区间找
left
=
mid
+
1
;
else
if
(
a
[
mid
]
>
k
)
//k较小时，在左半区间找
right
=
mid
-
1
;
else
//若想等则返回mid
return
mid
;
}
return
-
1
;
//找不到时返回-1
}