LeetCode Find Peak Element [TBD]
8914 ワード
対数時間の複雑さを書くといって、計算しても思いつかないで、O(n)の水を書きました
第2ラウンド:
A peak element is an element that is greater than its neighbors.
Given an input array where
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that
For example, in array
click to show spoilers.
Note:
Your solution should be in logarithmic complexity.
O(n)の
discuss(https://leetcode.com/discuss/23840/java-binary-search-solution)の中にlognが見つかりましたが、よく分かりません.
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 };