LeetCode Find Peak Element [TBD]

8914 ワード

対数時間の複雑さを書くといって、計算しても思いつかないで、O(n)の水を書きました
class Solution {

public:

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

        int len = num.size();

        if (len < 1) {

            return -1;

        }

        if (len == 1) {

            return 0;

        }

        bool asc = true;

        int idx = 0;

        int last = num[idx++];

        

        while (idx < len) {

            int cur = num[idx];

            if (asc) {

                if (cur < last) {

                    return idx - 1;

                }

            } else {

                if (cur > last) {

                    asc = true;   

                }

            }

            last = cur;

            idx++;

        }

        if (asc) {

            return idx - 1;

        }

        return -1;

    }

};

第2ラウンド:
A peak element is an element that is greater than its neighbors.
Given an input array where  num[i] ≠ num[i+1] , find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that  num[-1] = num[n] = -∞ .
For example, in array  [1, 2, 3, 1] , 3 is a peak element and your function should return the index number 2.
click to show spoilers.
Note:
Your solution should be in logarithmic complexity.
O(n)の
 1 // 9:43

 2 class Solution {

 3 public:

 4     int findPeakElement(vector<int>& nums) {

 5         int len = nums.size();

 6         if (len == 1) {

 7             return 0;

 8         }

 9         if (nums[0] > nums[1]) {

10             return 0;

11         }

12         

13         for (int i=1; i<len-1; i++) {

14             if (nums[i] > nums[i-1] && nums[i] > nums[i+1]) {

15                 return i;

16             }

17         }

18         return len-1;

19     }

20 };

discuss(https://leetcode.com/discuss/23840/java-binary-search-solution)の中にlognが見つかりましたが、よく分かりません.
 1 class Solution {

 2 public:

 3     int findPeakElement(vector<int>& nums) {

 4         int len = nums.size();

 5         int lo = 0, hi = len - 1;

 6         

 7         while (lo < hi) {

 8             int mid = (lo + hi) / 2;

 9             if (nums[mid] > nums[mid + 1]) {

10                 hi = mid;

11             } else {

12                 lo = mid + 1;

13             }

14         }

15         return lo;

16     }

17 };