leetcode[33. 搜索旋转排序数组]

2021-02-05 15:18

阅读：505

标签：查找旋转数组答案代码量判断序列 ems search

leetcode33. 搜索旋转排序数组

刚开始我的思路是先遍历直到发现断层，如果有与target一样的值就直接返回，否则就对断层的地方一直到最后进行二分查找。

class Solution {
public:
    int search(vector& nums, int target) {
        int ans = -1,pos = 0,n = nums.size();
        for(int i = 0; i  nums[i+1]) {pos = i+1; break;}
        }
        n = n-1;
        while(pos  target) n = mid-1;
        }
        return ans;
    }
};

但这样的最坏复杂度还是O(n)的，看了答案才知道像这样有只有一个断层的序列也能直接用二分.

class Solution {
public:
    int search(vector& nums, int target) {
        int i = 0,j = nums.size()-1,ans = -1;
        if(j+1 == 0) return -1;
        while(i = nums[0]){
                if(target = nums[0]) j = mid-1;
                else i = mid+1;
            }
            else{
                if(target >= nums[0] || target

而且题解中有一个代码量非常少的答案，思路和二分一样，只不过运用一些数学的判断让代码变得很简洁

总结：排好序的数组可以用二分查找，只有一个排序断层的数组也能直接用二分进行查找！

leetcode[33. 搜索旋转排序数组]

标签：查找旋转数组答案代码量判断序列 ems search

原文地址：https://www.cnblogs.com/Beic233/p/12787803.html

上一篇：js数组增删改，数组字符相互转化

下一篇：Java maven入门

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：leetcode[33. 搜索旋转排序数组]
文章链接：http://soscw.com/index.php/essay/51394.html

亲，登录后才可以留言！

leetcode[33. 搜索旋转排序数组]

评论

热门文章

推荐文章

最新文章

置顶文章