leetcode 链表题(LeetCode在排序数组中查找元素的第一个和最后一个位置34)
需求描述:给定一个按照升序排列的整数数组nums,和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值target,返回[-1,-1];
进阶:你可以设计并实现时间复杂度为O(logn)的算法解决次问题吗?
int main() {
// int nums[6] = {5,7,7,8,8,10};
int nums[2] = {2,2};
int returnSize = 0;
int* res = searchRange(nums, 2, 2, &returnSize);
for(int i=0;i<returnSize;i ) {
printf("%d ",res[i]);
}
printf("\n");
return 0;
}
#pragma mark - 在排序数组中查找元素的第一个和最后一个位置
int* returnDef(int* res,int* returnSize,int number) {
res[(*returnSize) ] = number;
res[(*returnSize) ] = number;
return res;
}
int binarySearch(int* nums,int target,int i,int j) {
while (i <= j) {
int m = (i j) / 2;
if(nums[m] == target) {
return m;
}else if (nums[m] < target) {
i = m 1;
}else {
j = m - 1;
}
}
return -1;
}
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
*returnSize = 0;
int* res = (int*)malloc(2000 * sizeof(int));
if(numsSize == 0) return returnDef(res,returnSize,-1);
if(numsSize == 1) {
if(nums[0] == target) return returnDef(res,returnSize,0);
return returnDef(res,returnSize,-1);
}
if(target > nums[numsSize -1] || target < nums[0]) return returnDef(res,returnSize,-1);
//采用二分查找
int i = 0;
int j = numsSize - 1;
int m = binarySearch(nums,target,i,j);
if(m >=0) {
*returnSize = 2;
int left = m;
while (left>=0 && nums[left] ==target) {
res[0] = left--;
}
int right = m;
while (right<numsSize && nums[right] == target) {
res[1] = right ;
}
return res;
}
//m < 0
return returnDef(res,returnSize,-1);
}
免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com