Leetcode-34. 在排序数组中查找元素的第一个和最后一个位置

描述

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]。

示例 1:

1
2
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

1
2
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

来源:力扣(LeetCode)
链接:34. Find First and Last Position of Element in Sorted Array

解题思路

这道题已经有提示使用二分查找,一开始我的思路是这样的,首先用二分查找找到一个下标index,如果nums[index] == target则设置两个变量startend,并且都初始化为index,然后两次循环,一个向左,一个向右,找到不等于target的元素,同时start--, end++更新左右下标。写了一段下面的代码,简直又丑又长,关键还没法通过所有的测试案例。后来对比了高手们的代码发现关键在于未对index是否已经位于边界的情况进行判断。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{

*returnSize = 2;

int* ret = (int *)malloc(sizeof(int) * 2);
memset(ret, -1, 2 * sizeof(int));


if(numsSize == 0) return ret;

if(numsSize == 1)
{
if(nums[0] != target)
{
return ret;
}
else
{
ret[0] = ret[1] = 0;
return ret;
}
}


if(numsSize == 2)
{
if(nums[0] == target && nums[1] != target)
{
ret[0] = 0;
ret[1] = 0;
return ret;
}
else if(nums[0] == target && nums[1] == target)
{
ret[0] = 0;
ret[1] = 1;
return ret;
}
else if(nums[0] != target && nums[1] == target)
{
ret[0] = 1;
ret[1] = 1;
return ret;
}
else
{
return ret;
}
}


int start = 0, end = numsSize - 1;
int index = -1;

while(start < end)
{
int mid = start + (end - start) / 2;

if(nums[mid] < target)
{
start = mid + 1;
}

else
{
end = mid;
}

}

if(nums[start] == target)
index = start;

if(index == -1)
return ret;

else
{
//if()

start = index;
end = index;

while(nums[start] == target && start > 0)
{
start--;
}

while(nums[end] == target && end < numsSize - 1)
{
end++;
}


}

ret[0] = start + 1;
ret[1] = end - 1;


return ret;

}

下面再来看看大神们的解法。

采用两次二分查找,第一次找到左边界,第二次找到右边界。具体代码如下:

代码

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
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{

*returnSize = 2;

int* ret = (int *)malloc(sizeof(int) * 2);
memset(ret, -1, 2 * sizeof(int));

int left = 0, right = numsSize;

//寻找左边界
while(left < right)
{
int mid = left + (right - left) / 2;
//注意这里的条件 是< 不是<=
if(nums[mid] < target) left = mid + 1;
else
right = mid;
}

//未找到相等的元素
if(right == numsSize || nums[right] != target)
return ret;

//找到并记录左边界
ret[0] = right;

//寻找有边界
left = 0;
right = numsSize;

while(left < right)
{
int mid = left + (right - left) / 2;
//注意这里的条件 是<= 不是<
if(nums[mid] <= target) left = mid + 1;
else
right = mid;
}

//有边界需要减1
ret[1] = right - 1;

return ret;

}

参考