153. Find Minimum in Rotated Sorted Array II

Posted on | In
Words count in article: 626 | Reading time ≈ 3

题目

Suppose an array sorted in ascending order 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:

1
2
Input: [1,3,5]
Output: 1

示例2：

1
2
Input: [2,2,2,0,1]
Output: 0

提示：

解法

解法一：

库函数

排序，取第一个即可。

JAVA

1
2
3
4
public int findMin(int[] nums) {
        Arrays.sort(nums);
    	return nums[0];
    }

解法二：

遍历

循环遍历，取最小的一个即可。

JAVA

1
2
3
4
5
6
7
8
9
public int findMin(int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
        	if (min > num) {
        		min = num;
        	}
        }
        return min;
    }

解法三：

找到最大值和最小值的交界

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findMin(int[] nums) {
		int i = 0;
		for (;i < nums.length - 1;i++) {
			if (nums[i + 1] < nums[i]) {
				return nums[i + 1];
			}
		}
		
		if (i == nums.length - 1) {
			return nums[0];
		}
		
		return -1;
	}

解法四：

二分查找

这块就不能用题目153的二分查找了。要稍微变形以下。

之前在使用二分查找的时候定义了三个值，low，mid，high。对应的nums数组中数字的关系，总共有6种，A3！。

分别是：

  • nums[low] <= nums[mid] <= nums[tail]
  • nums[mid] <= nums[tail] <= nums[low]
  • nums[tail] <= nums[low] <= nums[mid]

根据题目规则，已排序数组旋转，以下三种是不可能的情况：

  • nums[head] <= nums[tail] <= nums[mid]
  • nums[mid] <= nums[head] <= nums[tail]
  • nums[tail] <= nums[mid] <= nums[head]

JAVA

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 int findMin(int[] nums) {
		int low = 0;
		int high = nums.length - 1;

		while (low <= high) {
			int mid = low + (high - low) / 2;
			if (low == mid || high == mid) {
				return Math.min(nums[low], Math.min(nums[mid], nums[high]));
			}
			if (nums[low] <= nums[mid] && nums[mid] <= nums[high]) {
				// 单调递增数列
				// 1,1,2,3,4,5,5
				high--;
			} else if (nums[mid] <= nums[high] && nums[high] <= nums[low]) {
				// 后半段递增
				// 3,3,1,1,2,2
				high = mid;
			} else if (nums[high] <= nums[low] && nums[low] <= nums[mid]) {
				// 前半段递增
				// 2,2,3,4,5,1
				low = mid;
			}
		}
		return -1;
	}

解法五：

递归

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findMin(int[] nums) {
		return findMin(nums, 0, nums.length - 1);
	}

	public int findMin(int[] nums, int l, int r) {
		if (l == r) {
			return nums[l];
		}
		int mid = l + (r - l) / 2;
		if (nums[mid] < nums[r]) {
			// 后半段递增，则最小值在mid上或者mid左边
			return findMin(nums, l, mid);
		} else if (nums[mid] > nums[r]) {
			// 前半段递增
			return findMin(nums, mid + 1, r);
		} else {
			int le = findMin(nums, l, mid);
			int ri = findMin(nums, mid + 1, r);
			return Math.min(le, ri);
		}
	}
0%