题目:34. 在排序数组中查找元素的第一个和最后一个位置
力扣
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
解答:
方法一:直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见的下标,但这个方法的时间复杂度为 O(n^2),没有利用到数组升序排列的条件。
int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{
// 开辟两个int大小的空间放索引
int* res = (int*)malloc(sizeof(int) * 2);
// 判断是否找到target
int flag = 0;
int i = 0;
while (i < numsSize)
{
// 找到target,flag置1
if (nums[i] == target)
{
flag = 1;
break;
}
i++;
}
// 没找到target,返回[-1,-1]
if (flag == 0)
{
res[0] = -1;
res[1] = -1;
*returnSize=2;
return res;
}
// 程序走到这里,一定存在索引
// 先记录第一个索引位置
res[0] = i;
// 寻找结束位置
while (i < numsSize && nums[i] == target)
{
i++;
}
// 再记录结束索引位置
res[1] = i - 1;
*returnSize=2;
return res;
}
方法二:由于数组已经排序,因此整个数组是单调递增的,我们可以利用二分法来加速查找的过程。
其实我们要找的就是数组中「第一个等于target的位置」和「第一个大于target的位置减一」
c代码
// 找出给定目标值在数组中的开始位置
int findFitstPosition(int* nums, int numsSize, int target)
{
if(numsSize==0)
return -1;
int size = numsSize;
int left = 0;
int right = size - 1;
while (left < right)
{
// 取下界
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] == target)
// 即使nums[mid] == target,也要right = mid
// 使得下标向target的第一个位置靠拢
right = mid;
else
// nums[mid] > target
right = mid - 1;
}
// left == right
if (nums[left] != target)
return -1;
return left;
}
// 找出给定目标值在数组中的结束位置
int findLastPosition(int* nums, int numsSize, int target)
{
if(numsSize==0)
return -1;
int size = numsSize;
int left = 0;
int right = size - 1;
while (left < right)
{
// 取上界
int mid = left + (right - left + 1) / 2;
if (nums[mid] > target)
right = mid - 1;
else if (nums[mid] == target)
// 使得下标向target的最后一个位置靠拢
left = mid;
else
// nums[mid] < target
left = mid + 1;
}
// left == right
if (nums[left] != target)
return -1;
return left;
}
// 在排序数组中查找元素的第一个和最后一个位置
int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{
int* ans=(int*)malloc(sizeof(int)*2);
int size = numsSize;
int fitstPosition = findFitstPosition(nums, numsSize, target);
// 整数数组为空 或者 没有找到target
// 直接返回[-1,-1]
// 两种情况放在一起的话,前面的两个函数要先排除size=0的情况
// 否则 right = size-1 < 0
// 代码复用,更加简洁
if (size == 0 || fitstPosition == -1)
{
ans[0]=-1;
ans[1]=-1;
*returnSize=2;
return ans;
}
int lastPosition = findLastPosition(nums, numsSize, target);
ans[0]=fitstPosition;
ans[1]=lastPosition;
*returnSize=2;
return ans;
}
cpp代码
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
private:
int findFitstPosition(vector<int> &nums, int target)
{
int size = nums.size();
int left = 0;
int right = size - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] == target)
right = mid;
else
right = mid - 1;
}
if (nums[left] != target)
return -1;
return left;
}
int findLastPosition(vector<int> &nums, int target)
{
int size = nums.size();
int left = 0;
int right = size - 1;
while (left < right)
{
int mid = left + (right - left + 1) / 2;
if (nums[mid] > target)
right = mid - 1;
else if (nums[mid] == target)
left = mid;
else
left = mid + 1;
}
if (nums[left] != target)
return -1;
return left;
}
public:
vector<int> searchRange(vector<int> &nums, int target)
{
int size = nums.size();
if (size == 0)
return {-1, -1};
int fitstPosition = findFitstPosition(nums, target);
if (fitstPosition == -1)
return {-1, -1};
int lastPosition = findLastPosition(nums, target);
return {fitstPosition, lastPosition};
}
};