[leetcode] 33. Search in Rotated Sorted Array解題報告

3297 ワード
LeetCode アルゴリズム#アルゴリズム# search binary
タイトルリンク:https://leetcode.com/problems/search-in-rotated-sorted-array/
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,  0 1 2 4 5 6 7  might become  4 5 6 7 0 1 2 ).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
構想:回転配列なので、左へ検索すべきか右へ検索すべきかを決定するのは面倒です.私の解決方法は2つの二分で、1つの二分で右配列の左端点を見つけて、このように2つの配列の境界を確定して、それからtargetが配列の最後の値より大きいかどうかによって左または右配列を検索するかを確定します.
targetが配列の最後の値より大きい場合、targetは左配列でしか検索できないことを示します.
targetが配列の最後の値より小さい場合は、targetが右配列で検索されることを示します.
このように分けたほうが分かりやすく、間違いもしにくいと思います.
コードは次のとおりです.
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size(),left = 0, right = len -1; 
        if(len == 0) return -1;
        while(left < right)//            
        {
            int mid = (left + right)/2;
            if(nums[mid] < nums[right])
                right = mid;
            else
                left = mid + 1;
        }
        int low = (target > nums[len-1])?0:right;//        
        int high = (target > nums[len-1])?(right-1):(len-1);
        while(low <= high)//           ，       ^@^
        {
            int mid = (low + high)/2;
            if(nums[mid] < target)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return nums[low]==target?low:-1;
    }
};

また、もっと正統な方法は1回2点をして、左か右かを分析することです.2分ごとに3つの状況があります.
1.nums[mid]=target、midを返す
2.nums[mid]1)nums[mid]2)そうでなければ左区間で左区間を検索し、right=mid-1;
3.nums[mid]>=nums[right]で、[elft,mid]区間が左のインクリメント区間であることを説明し、targetがこの左の区間にあるか否かを判断する
1)nums[left]<=target2)そうでなければtargetが[mid,right]の不規則区間で右区間を検索するとleft=mid+1となる.
次に、境界条件を考慮します.
配列長が1の場合、left=right、mid=left=right、nums[mid]=targetの場合、直接戻ります.そうしないと条件3に入り、ループが終了し、-1に戻ります.
コードは次のとおりです.
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size(),left = 0, right = len -1; 
        while(left <= right)//            
        {
            int mid = (left + right)/2;
            if(nums[mid] == target) return mid;
            if(nums[mid] < nums[right])
            {
                if(target > nums[mid] && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid -1;
            }
            else
            {
                if(target >= nums[left] && target < nums[mid])
                    right = mid -1;
                else
                    left = mid + 1;
            }
        }
        return -1;
    }
};

2つ目の方法の参考:http://bangbingsyb.blogspot.com/2014/11/leetcode-search-in-rotated-sorted-array.html
2つのブランチ間でmergeした場合の状態遷移について整理
Sveltekitアクセシビリティ試験:自動CI A 11 Y試験