153. Find Minimum in Rotated Sorted Array

Posted on | In
Words count in article: 578 | 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.

You may assume no duplicate exists in the array.

Example 1:

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

Example 2：

1
2
Input: [4,5,6,7,0,1,2]
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
15
16
17
18
19
20
public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        
        if (nums[low] < nums[high]) {
        	return nums[low];
        }
        
        while (low < high) {
        	int mid = low + (high - low) / 2;
        	if (nums[mid] < nums[high]) {
        		// mid 到 high 是递增的，说明最小元素在mid左侧，或者就是mid
        		high = mid;
        	} else {
        		low = mid + 1;
        	}
        }
        
        return nums[low];
    }

解法四：二分查找-递归

JAVA

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

	public int findMin(int[] nums, int low, int high) {
		if (low == high) {
			return nums[low];
		}
		int mid = low + (high - low) / 2;
		if (nums[mid] < nums[high]) {
			// mid 到 high 是递增的，说明最小元素在mid左侧，或者就是mid
			return findMin(nums, low, mid);
		} else {
			return findMin(nums, mid + 1, high);
		}
	}

解法五：二分查找变形

通过二分查找的方法，找到这个数列的最大值。

因为这个数列是一个排序数列变形而来，那么紧跟在最大数字之后的数字，一定是最小的数字。

因此，求出最大数字的索引，加1返回即可。

注意一下，如果最大数字索引是数组长度-1的话，返回第一个元素的索引即可。

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findMin(int[] nums) {
		int index = 0;
		int n = nums.length;

		for (int b = n / 2; b >= 1; b /= 2) {
			while (index + b < n && nums[index + b] > nums[index]) {
				index += b;
			}
		}

		if (index == nums.length - 1) {
			return nums[0];
		} else {
			return nums[index + 1];
		}
	}

解法六：分治法

Java

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

	private int findMin(int[] nums, int left, int right) {
		// One or two elements
		if (left + 1 >= right)
			return Math.min(nums[left], nums[right]);

		// Sorted
		if (nums[left] < nums[right])
			return nums[left];

		int mid = left + (right - left) / 2;

		// to find the solution recursively
		return Math.min(findMin(nums, left, mid - 1), findMin(nums, mid, right));
	}
0%