34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-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]
示例 3:
输入:nums = [], target = 0 输出:[-1,-1]
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
是一个非递减数组-109 <= target <= 109
暴力遍历两边
/**
* Note: The returned array must be malloced, assume caller calls free().
返回的数组必须被 malloced
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
// int dp[numsSize];
int i, a = -1, b = -1;
*returnSize = 2;
// 返回大小为 *returnSize =2的数组
for (i = 0; i < numsSize; i++) {
// dp[i]=0;
if (nums[i] == target)
// dp[i] = 1;//和目标值相同置1,否则置0
{
a = i;
break;
}
}
for (i = numsSize - 1; i >= 0; i--) {
if (nums[i] == target) {
b = i;
break;
}
}
//返回的数组必须被 malloced
int* c = (int*)malloc(sizeof(int) * 2);
// int c[2]={a,b};//错误方式
c[0] = a;
c[1] = b;
return c;
}