昇順でソートされた整数配列を指定し、指定されたターゲット値の開始位置と終了位置を見つけます.アルゴリズムの実行時の複雑さはO(log n)の順序でなければなりません.
1997 ワード
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int low_i,low_j,high_i,high_j;
int low_middle,high_middle;
low_i = 0;
low_j = numsSize-1;
*returnSize=2;
int *res = (int*)calloc(2, sizeof(int));
res[0] = -1;
res[1] = -1;
while(low_i<=low_j)
{
low_middle = (low_i+low_j)/2;
if(nums[low_middle]==target)
{
if(low_middle==0) break;
else
{
if(nums[low_middle-1]target) break;
else high_i = high_middle+1;
}
}
else
high_j = high_middle-1;
}
res[0] = low_middle;
res[1] = high_middle;
return res;
}
考え方:二分検索を使用して、目標値の低位下標と高位下標を検索します.4つの変数を設定し、下位下位および上位下位の検索の開始位置を表します.絶えず2点探して、最終的に目標を見つけます!
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int low_i,low_j,high_i,high_j;
int low_middle,high_middle;
low_i = 0;
low_j = numsSize-1;
*returnSize=2;
int *res = (int*)calloc(2, sizeof(int));
res[0] = -1;
res[1] = -1;
while(low_i<=low_j)
{
low_middle = (low_i+low_j)/2;
if(nums[low_middle]==target)
{
if(low_middle==0) break;
else
{
if(nums[low_middle-1]target) break;
else high_i = high_middle+1;
}
}
else
high_j = high_middle-1;
}
res[0] = low_middle;
res[1] = high_middle;
return res;
}