33. Search in Rotated Sorted Array
2628 ワード
問題の説明
整数型配列numsは、繰り返しずに昇順に配列される.
関数の前にnumsは任意のpivotインデックスk(1<=k
ループを完了する配列numsに、整数targetに、numsに存在するtargetのインデックスを検索します.存在しない場合は、-1が出力されます.
必ずO(logn)で時間の複雑さを実現しなければならない.
出力例
方法
初めての試み
一般的な二分探索では、ゼロインデックスの値を考慮すべきですか?
もう一つの基準を増やして実施する.
配列は増加してから減少してから増加する様子を呈している.
ターゲット値がnums[0]より大きい場合、ターゲット値は増加します.
ターゲット値がnums[0]を基準として小さい場合、増分後の最小値インデックスから最後のインデックスまでの間に存在します.
2つに分けた後、2つのナビゲーションの中間値(mid)とnums[0]を比較して、それらが同じようにどこにあるかを決定します.
そしてstartとend値を調整し、二分探索を行い、、、!
ソースコード
class Solution {
public:
int search(vector<int>& nums, int target) {
int start=0;
int end = nums.size()-1;
int mid;
if(nums[0] > target){
while(start <= end){
mid = (start + end)/2;
//증가하는 부분에 mid 위치
if(nums[0] <= nums[mid]){
start = mid+1;
}
//증가했다가 감소하는 부분에 mid 위치
else{
if(nums[mid] > target){
end = mid -1;
}
else if(nums[mid] < target){
start = mid+1;
}
else return mid;
}
}
}
else if (nums[0] < target){
while(start<=end){
mid = (start + end)/2;
//증가하는 부분에 mid 위치
if(nums[0] <= nums[mid]){
if(nums[mid] > target){
end = mid -1;
}
else if(nums[mid] < target){
start = mid+1;
}
else return mid;
}
//증가했다가 감소하는 부분에 mid 위치
else{
end = mid - 1;
}
}
}
else return 0;
return -1;
}
};
レビュー
最初は問題が急に理解できなくなりました.コードを効率的に記述する方法が重要な問題のようです.
実行時間は4 msで悪くはありませんが、コードが汚いです.
Reference
この問題について(33. Search in Rotated Sorted Array), 我々は、より多くの情報をここで見つけました https://velog.io/@mm723/33.-Search-in-Rotated-Sorted-Arrayテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol