首页 > itarticle > leetcode binary search 162. Find Peak Element

leetcode binary search 162. Find Peak Element

admin 11月 12, 2020 0

Suppose a sorted array is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).Find the minimum element.You may assume no duplicate exists in the array. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
public class  {
    public int findMin(int[] nums) {
        int index = 0;
        int left = 0;
        int right = nums.length - 1;
        int size = nums.length;
        
        if(size == 1) return nums[0];
        if(nums[0] < nums[right]) return nums[0];
        if(nums[right] < nums[right - 1]) return nums[right];

        while(left <= right) {
            int mid = (left + right) / 2;
            if(mid != 0 && nums[mid] < nums[mid - 1]) {
                index = mid;
                break;
            } else if(nums[mid] < nums[0]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return nums[index];
    }
}

162. Find Peak Element

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.
求局部最小／最大值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
public class  {
    public int findPeakElement(int[] nums) {
        int size = nums.length;
        if(size == 1 || nums[0] > nums[1]) return 0;
        if (nums[size - 1]>nums[size-2]) return size - 1;
        if(size == 2) return 1;

        int left = 0;
        int right = size - 1;
        int index = 0;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if( nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
                index = mid;
                break;
            } else if(nums[mid] < nums[mid + 1] ) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return index;
    }
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能