统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
限制：
0 <= 数组长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解 :
代码如下 :
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
|
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return 0;
// 二分法找 值为target 的最右边索引
int right = 0;
int begain = 0, end = nums.length - 1;
while (begain <= end){
int mid = (begain + end) >> 1;
if (nums[mid] <= target){
// 往右边找
begain = mid + 1;
}else {
// 往左边找
end = mid - 1;
}
}
right = begain;
// 如果没找到
if(end >= 0 && nums[end] != target) return 0;
// 二分法找 值为targe 的最左边索引
int left = 0;
begain = 0;
end = nums.length - 1;
while (begain <= end){
int mid = (begain + end) >> 1;
if (nums[mid] >= target){
// 往左边找
end = mid - 1;
}else {
// 往右边找
begain = mid + 1;
}
}
left = end;
return right - left - 1;
}
|
优化
- 边代码过于臃肿，有两遍 二分搜索 的代码 几乎一样
- 所以下边，我们尝试优化代码，将 二分搜索的代码提取公用方法
- 提取binarySearch方法，查找 target 在 nums数组中的右边界的下一个数字
- 因为此题目中，数组中数字都是int整数
- 所以，binarySearch 查找 target 的 右边界 - target-1的右边界
- 即可得到最终结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public int search1(int[] nums, int target) {
// 因为此题目中，数组都为int整数
// 所以，binarySearch查找 target 右边界，再查找 target - 1的右边界
// 相减 即可 得到 结果
return binarySearch(nums, target) - binarySearch(nums, target - 1);
}
// 二分查找 右边界
// 其实就是查找 target 右边 第一个不为 target 的下标
int binarySearch(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;
}
|
复杂度分析 :
时间复杂度 : O(log N)
空间复杂度 : O(1)
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解 :
- 此题目与第一个道题，基本一致
- 不同之处仅在于结果的最终输出形式
- 这里不再赘述了，直接贴代码
代码如下 :
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
|
public static int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) return new int[]{-1,-1};
// 二分法找 值为target 的最右边索引
int right = 0;
int begain = 0, end = nums.length - 1;
while (begain <= end){
int mid = (begain + end) >> 1;
if (nums[mid] <= target){
// 往右边找
begain = mid + 1;
}else {
// 往左边找
end = mid - 1;
}
}
right = begain;
// 如果没找到
if (end < 0 || nums[end] != target) return new int[]{-1,-1};
// 二分法找 值为targe 的最左边索引
int left = 0;
begain = 0;
end = nums.length - 1;
while (begain <= end){
int mid = (begain + end) >> 1;
if (nums[mid] >= target){
// 往左边找
end = mid - 1;
}else {
// 往右边找
begain = mid + 1;
}
}
left = end;
int[] res = new int[2];
res[0] = left + 1;
res[1] = right - 1;
return res;
}
|
优化
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
|
public static int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) return new int[]{-1,-1};
int right = binarySearch(nums, target);
int left = binarySearch(nums, target - 1);
// 判断left有效性
// 不在范围， 或者其值 != target。 则说明没找到元素
if (left < 0 || left >= nums.length || nums[left] != target) return new int[]{-1,-1};
return new int[]{left, right - 1};
}
// 找右边界
public static int binarySearch(int[] nums, int target){
int begain = 0, end = nums.length - 1;
while (begain <= end){
int mid = (begain + end) >> 1;
if (nums[mid] <= target){
begain = mid + 1;
}else {
end = mid - 1;
}
}
return begain;
}
|
复杂度分析 :
时间复杂度 : O(log N)
空间复杂度 : O(1)
总结
- 通过这两道题，至少学会了一个知识点
- 之前只用二分来查找排序数组中，是否存在某元素
- 现在学会了，通过二分查找，查找元素在数组中的起始位置 和 结束位置
- 其实重点，就在 = 时逻辑的处理
- 在查找右边界时 <= 都往右查找
- 在查找左边界时 >= 都往左查找