当前位置

网站首页> 程序设计 > 开源项目 > 程序开发 > 浏览文章

[Leetcode] Find Minimum in Rotated Sorted Array 找旋转有序数组的最小值

作者:小梦 来源: 网络 时间: 2024-01-20 阅读:

Find Minimum in Rotated Sorted Array I

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.

二分迭代法

复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

找旋转数组的起点,实际上类似找一个山谷,只要两边都比中间高就对了,这和Find Peak Element这题很像。我们不断地取中点,找左右两侧较小的那一侧,直到找到一个点比左右两边都低。

注意

在二分到两头的时候要特殊处理一下,返回两头和两头第二个中最小的。

代码

public class Solution {

public int findMin(int[] nums) {    for(int min = 0, max = nums.length - 1, mid = max / 2; min <= max; mid = (min + max)/2){        if(mid == 0) return Math.min(nums[mid],nums[max]);        if(mid == nums.length - 1) return Math.min(nums[mid],nums[min]);        if(nums[mid] < nums[mid-1] && nums[mid] < nums[mid+1]) return nums[mid];        if(nums[mid] > nums[max]){min = mid + 1;        } else {max = mid - 1;        }    }    return nums[0];}

}

二分迭代法

复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

递归法实现起来更加简洁清晰。判断条件是mid的值比mid-1的值要大。

代码

public class Solution {    public int findMin(int[] num) {        return findMin(num,0,num.length-1);    }    private int findMin(int[] num, int low, int high){        if(low>=high){return num[low];        }        int mid = (low+high)/2;        if(mid>0&&num[mid]<num[mid-1]) return num[mid];        if(num[high]<num[mid]) return findMin(num,mid+1,high);        else return findMin(num,low,mid-1);    }}

Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why? 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.

The array may contain duplicates.

二分递归法

复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

如果有重复的话,一旦中间和右边是相等的,就无法确定是否在左半边还是右半边,这时候我们必须对两边都递归求解。如果中间大于右边界,则肯定在右半边,如果中间小于右边界,则肯定在左半边。如果中间等于右边界,则两个半边都有可能。

代码

public class Solution {    public int findMin(int[] nums) {        return findMin(nums, 0, nums.length - 1);    }        public int findMin(int[] nums, int min , int max){        int mid = (min + max) / 2;        if(min == max){return Math.min(nums[min],nums[max]);        }        int right = Integer.MAX_VALUE, left = Integer.MAX_VALUE;        if(nums[mid] > nums[max]){right = findMin(nums, mid + 1, max);        } else if (nums[mid] < nums[max]) {left = findMin(nums,min, mid);        } else {right = findMin(nums, mid + 1, max);left = findMin(nums,min, mid);        }        return Math.min(right,left);    }}

热点阅读

网友最爱