首页 > 代码库 > LeetCode 154 Find Minimum in Rotated Sorted Array II

LeetCode 154 Find Minimum in Rotated Sorted Array II

2024-07-28 14:50:14   228人阅读

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.

思路1：采用排序（jdk中的快排），时间复杂度为O(nlogn)，代码如下
public class Solution {
	public int findMin(int[] num) {
		Arrays.sort(num);
		return num[0];
	}
}

思路2：采用一次性遍历，时间复杂度为O(n)，代码如下
public class Solution {
    public int findMin(int[] num) {
        int  min=Integer.MAX_VALUE;
        for(int i=0;i<num.length;i++){
        	if(min>num[i])
        		min=num[i];
        }
        return min;
    }
}
思路3：采用折半查找，时间复杂度为O(logn)，代码如下
public class Solution {
	public int findMin(int[] num) {
		return minFind(num, 0, num.length - 1);
	}

	private int minFind(int[] num, int begin, int end) {
		int middle = (begin + end) / 2;
		if (begin == end) {
			return num[begin];
		} else if (end == begin + 1) {
			return Math.min(num[begin], num[end]);
		} else if (end == begin + 2) {
			return Math.min(Math.min(num[begin], num[begin + 1]), num[end]);
		}
		if (num[begin] == num[end]) {
			return Math.min(minFind(num, begin, middle),minFind(num, middle, end));
		}
		if (num[middle] < num[begin] && num[middle] <= num[end]) {
			return minFind(num, begin, middle);
		} else if (num[begin] <= num[middle] && num[end] < num[middle]) {
			return minFind(num, middle, end);
		} else if (num[begin] < num[middle] && num[middle] <= num[end]) {
			return minFind(num, begin, middle);
		}else if (num[begin] <= num[middle] && num[middle] < num[end]) {
			return minFind(num, begin, middle);
		}
		return 0;
	}
}


LeetCode 154 Find Minimum in Rotated Sorted Array II


联系
我们