題目
給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums士复，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開(kāi)始位置和結(jié)束位置。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別我擂。
如果數(shù)組中不存在目標(biāo)值，返回 [-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]
思路
采用雙指針?lè)ㄐＤΓ瑥拈_(kāi)頭和結(jié)尾分別搜索target，一開(kāi)始代碼很簡(jiǎn)單阶淘，但是考慮因素不全衙吩，加了一堆if else判斷
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> result;
if (nums.size() ==0)
{
result.push_back(-1);
result.push_back(-1);
return result;
}
int left = 0, right = nums.size() - 1;
while (right > left)
{
do
{
++left;
}
while (nums[left] != target && left < nums.size() - 1);
do
{
--right;
}
while (nums[right] != target && right > 0);
}
if (nums.size() == 1 && nums[0] == target)
{
result.push_back(0);
result.push_back(0);
return result;
}
else if (nums.size() == 1 && nums[0] != target)
{
result.push_back(-1);
result.push_back(-1);
return result;
}
else if (right == 0 && left == nums.size() -1 && nums[left] != nums[right] )
{
result.push_back(-1);
result.push_back(-1);
return result;
}
else if (nums[left] == target && nums[right] == target)
{
result.push_back(right);
result.push_back(left);
return result;
}
}
};
int main(int argc, char* argv[])
{
vector<int> test = { 5,7,7,8,8,10 };
int target = 8;
vector<int> result = Solution().searchRange(test, target);
system("pause");
return 0;
}
