leetcode 153. 寻找旋转排序数组中的最小值

大耗子 2021年02月20日 13次浏览

题目: 153. 寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值

难度中等

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]

请找出其中最小的元素。

示例 1:

输入:nums = [3,4,5,1,2]
输出:1

示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0

示例 3:

输入:nums = [1]
输出:1

提示:

  • 1 <= nums.length <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数都是 唯一
  • nums 原来是一个升序排序的数组,但在预先未知的某个点上进行了旋转

解题思路

二分法:

只要找到的mid < end,说明递减序列再左边。

反则说明再右边。

因为如果mid与end相等的话,就不确定是左边还是右边,所以说的左边与右边都是包含了mid的,意思是他们的交集是mid位置。

这个题目如果不限制数字唯一的话,有可能start,mid, end三个位置数字相等, 此时无法得知递减序列是在mid的左边还是右边,此时只能通过遍历寻找。

代码

class Solution {
public:

	int findMin1(vector<int>& nums) {
		if (nums.size() == 1) return nums[0];
		int start = 0, end = nums.size() - 1;
		int mid = (start + end) >> 1;

		// 如果第一个比最后一个小,那直接返回第一个
		while (nums[start] >= nums[end]) {
			// 只剩下两个,那肯定是右边那个,因为肯定不满足右边比左边大
			if (end - start == 1) {
				return nums[end];
			}
			mid = (start + end) >> 1;
			// 因为右可能出现start, mid, end都相等的情况,单此时无法得知是再左边还是右边,只能通过遍历了
			if (nums[start] == nums[end] && nums[start] == nums[mid])
				return findlose(nums, start, end);

			if (nums[mid] > nums[end]) {
				start = mid;
			}
			else {
				end = mid;
			}
		}
		return nums[start];
	}

	int findlose(vector<int>& nums, int start, int end) {
		int ret = nums[0];
		for (int i = 1; i <= end; i++)
		{
			if (ret > nums[i])
				return nums[i];
		}	
		return ret;
	}

	int findMin(vector<int>& nums) {
		if (nums.size() == 1) return nums[0];
		int start = 0, end = nums.size() - 1;
		int mid = (start + end) >> 1;

		while (start < end) {

			mid = (start + end) >> 1;
			if (nums[mid] > nums[end]) {
				start = mid+1;
			}
			else {
				end = mid;
			}
		}
		return nums[start];
	}


};