剑指 Offer 11. 旋转数组的最小数字

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1

示例 2：

输入：[2,2,2,0,1]
输出：0

思路

golang

1.暴力搜索比较最小值，最容易想到的是这种方法，返回数组中的最小值，也可以通过

时间复杂度：O(n)

func minArray(numbers []int) int {
    var min = numbers[0]
    for i:=1;i<len(numbers);i++{
        if min > numbers[i]{
            min = numbers[i]
        }
    }
    return min
}

2.采用二分法的思想，寻找旋转数组的最小元素是将原来的有序数组将一部分旋转到前面，再查找最小值，属于部分有序。

• 初始化： 声明 left, right 双指针分别指向 nums数组左右两端；
• 循环二分： 设 mid = (left+right)/2为每次二分的中点，可分为以下三种情况：
• 当 nums[mid] > nums[right]时： mid一定在 左排序数组 中，即旋转点 x一定在 [mid+1,right] 闭区间内，因此执行 left = mid + 1；
• 当 nums[mid] < nums[right] 时： mid一定在 右排序数组 中，即旋转点 x一定在[left,mid] 闭区间内，因此执行 right = mid；
• 当 nums[mid] == nums[right]时： 无法判断 mid 在哪个排序数组中，即无法判断旋转点 x 在 [left,mid] 还是 [mid+1,right] 区间中。解决方案： 执行 right-- 缩小判断范围
• 返回值： 当 i = ji=j 时跳出二分循环，并返回 旋转点的值 nums[i]nums[i] 即可。

可能会有以下问题：

1. 为什么right=mid 而 left = mid+1?

2. 为什么right--不会对结果产生影响？

因为我们执行的条件是当nums[mid]==nums[right]，说明此时元素不是数组中最小元素，而题目所给是删除最小的唯一元素。

//采用二分法
func minArray(numbers []int) int {
	left, right := 0, len(numbers)-1

	for left < right { //退出条件
		mid := left + (right-left)/2
		if numbers[mid] > numbers[right] { //1.最小值在[mid+1,right]区间内
			left = mid + 1
		} else if numbers[mid] < numbers[right] { //2.最小值在[left,mid]区间内
			right = mid
		} else { //3.存在重复数字，缩小区间查找范围
			right--
		}
	}
	return numbers[left]
}

js

/**
 * @param {number[]} numbers
 * @return {number}
 */

//1.直接采用js的函数Math.min()
var minArray = function(numbers) {
    return Math.min(...numbers)
};

//2.采用Js的sort函数将数组重排，取第0个元素
//如果没有指明 compareFunction ，元素会按照转换为的字符串的诸个字符的Unicode位点进行排序。
var minArray = function(numbers) {
    numbers.sort((a,b)=>a-b) //升序排序
    return numbers[0]
};

//3.采用二分法可以将O(n)时间复杂度降低到O(logn)
var minArray = function(numbers) {
    let left = 0,right = numbers.length-1;

    while(left<right){
        //向下取整
        let mid = left + Math.floor((right - left) / 2) 
        if(numbers[mid] < numbers[right]) right = mid;
        else if(numbers[mid] > numbers[right]) left = mid+1;
        else right--;
    }
    return numbers[left];
};

剑指 Offer 11. 旋转数组的最小数字

原文：https://www.cnblogs.com/zmk-c/p/14622667.html