练习讲题
/*
O(logn) && O(1)
Note:
binary search
什么时候可以while(l <= r). 当跳出条件是
if(nums[mid] == target)
取等号会死循环时用while(l < r)
if (nums[mid] > nums[mid + 1])
r = mid;
*/
public class Solution {
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1])
r = mid;
else
l = mid + 1;
}
return l;
}
}
/*
面试时:
1. 问清楚You may imagine that nums[-1] = nums[n] = -∞.
2. 分cases讨论清楚
(1) All the numbers appear in a descending order.
(2) All the elements appear in ascending order.
(3) The peak appears somewhere in the middle.
*/
class Solution {
public int findPeakElement(int[] nums) {
for(int i = 0; i < nums.length - 1; i++) {
if(nums[i] > nums[i + 1])
return i;
}
return nums.length - 1;
}
}
/*
O(logn)
O(logn)
*/
public class Solution {
public int findPeakElement(int[] nums) {
return search(nums, 0, nums.length - 1);
}
public int search(int[] nums, int l, int r) {
if (l == r)
return l;
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1])
return search(nums, l, mid);
return search(nums, mid + 1, r);
}
}