[Leetcode]寻找峰值

题目

思路

如果常规解法不考虑时间复杂度，直接遍历即可得到峰值，时间复杂度为O(n)，题目要求O(logn)，因此我们需要使用二分法。

首先考虑题目要求：nums[-1]=nums[n]=-∞，因此在数组开始必然存在一个上坡，在结尾必然存在一个下坡。

这里给一个例子：[1，3，2，0]，这里按照二分法一开始mid选的值为3，我们发现3大于2，因此有了一个下坡，而数组一开始又有一个上坡，这样说的话，只要往数组前半部分寻找，如果找到比3大的数，那么必然有一个峰值（因为有一个上坡，又有一个下坡），如果找到比3小的数，那么肯定也能有一个峰值，反之肯定也能找到一个峰值，如果不理解的话自己列一个例子去一步一步试试就知道了。

代码

int findPeakElement(const vector<int> &num) {

        int start = 0,end=num.size()-1;

        int mid = start + (end - start) / 2;

        while(start <= end)

        {

            //找完了

            if(start == end) return start;

            mid = start + (end - start) / 2;

            //往后面寻找

            if(num[mid] < num[mid+1])

            {

                start = mid + 1;

            }//往前面寻找

            else

            {

                end = mid;

            }

        }

        return 0;

    }

巴特西

[Leetcode]寻找峰值

题目

思路

代码

最新文章

热门文章