首页 > 代码库 > 【leetcode】Find Minimum in Rotated Sorted Array II JAVA实现

【leetcode】Find Minimum in Rotated Sorted Array II JAVA实现

一、题目描述

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.

 

这道题目就是Find Minimum in Rotated Sorted Array的增强版,在数组中增加了重复的元素。

具体的解法在http://www.cnblogs.com/rolly-yan/p/4032167.html中进行了详细的分析,如有需要请参考。

 

二、代码实现

package com.edu.leetcode;public class FindMinimuminRotatedSortedArray {		public int findMin(int[] num) {		int start=0; 		int end=num.length-1;					while(num[start]>=num[end]){                      //num[start]>=num[end]说明数组不是正向有序的,最小值不在第一个位置						if(end-start==1){			//循环结束的条件,当只有两个元素的				return num[end];			}			int mid=(start+end)/2;						if(num[start]==num[mid]&&num[mid]==num[end]){    				//有这个条件有两种情况:1、当只有一个元素时;				//2、当数组中有大量重复的元素时,不可以再使用对半查找				int minValue=http://www.mamicode.com/num[start];>

  

【leetcode】Find Minimum in Rotated Sorted Array II JAVA实现