旋转数组的最小数字

1. 题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

2. 思路

• 第一种：顺序查找，效率O（N）
• 第二种：二分查找。对比寻找旋转排序数组中的最小值.md这道题有重复的元素

3. 实现

3.1. 顺序查找

• java

public class 旋转数组的最小数字
{
    public static void main(String[] args)
    {
        System.out.println(new 旋转数组的最小数字().minNumberInRotateArray(new int[]{3,4,5,1,2}));
        System.out.println(new 旋转数组的最小数字().minNumberInRotateArray(new int[]{5,1,2,3,4}));

    }

    public int minNumberInRotateArray(int[] array)
    {
        //检查参数
        if (array == null || array.length == 0)
        {
            return 0;
        }
        int min = array[0];
        for (int val : array)
        {
            if (val < min)
            {
                min = val;
            }
        }
        return min;

    }
}

• go

//暴力法
//时间：O(n)
//空间：O(1)
func MinNumberInRotateArray(rotateArray []int) int {
	if len(rotateArray) == 0 {
		return 0
	}

	min := rotateArray[0]
	for _, val := range rotateArray {
		if val < min {
			min = val
		}
	}

	return min
}

3.2. 二分查找

• java

public class 旋转数组的最小数字
{
    public static void main(String[] args)
    {
        System.out.println(new 旋转数组的最小数字().minNumberInRotateArray(new int[]{3, 4, 5, 1, 2}));
        System.out.println(new 旋转数组的最小数字().minNumberInRotateArray(new int[]{5, 1, 2, 3, 4}));
        System.out.println(new 旋转数组的最小数字().minNumberInRotateArray(new int[]{1, 1, 1, 0, 1 }));
    }

    //二分查找
    private int binarySearch(int[] array)
    {
        int left = 0;
        int right = array.length - 1;
        while (left <= right)
        {
            int mid = (left + right) >>> 1;
            //如果中间的数比右边的数小，说明右边是顺序增长的，那么最小的数肯定在左边 1,2,3,4,5 -> 5,1,2,3,4
            if (array[mid] < array[right])
            {
                right = mid;
            }
            //如果含有重复的，只能逐步缩小右边界，最坏退化成O(n)
            else if (array[mid] == array[right])
            {
                right = right - 1;
            }
            //如果中间的数比右边的数大，说明右边是断崖的，那么最小的数肯定在右边 1,2,3,4,5 -> 3,4,5,1,2
            else
            {
                left = mid + 1;
            }
        }

        return left;
    }

    public int minNumberInRotateArray(int[] array)
    {
        //检查参数
        if (array == null || array.length == 0)
        {
            return 0;
        }
        return array[this.binarySearch(array)];

    }
}

• go

//二分
//时间：平均O(logn)，最坏O(n)
//空间：O(1)
//[3,4,5,1,2] 5>2，那么去右边找
//[5,1,2,3,4] 2<4，那么去左边找
func MinNumberInRotateArray2(rotateArray []int) int {
	if len(rotateArray) == 0 {
		return 0
	}

	left := 0
	right := len(rotateArray) - 1
	for left < right {
		if rotateArray[left] < rotateArray[right] {
			return rotateArray[left]
		}

		mid := (left + right) >> 1
		//跟右端点比较
		if rotateArray[mid] > rotateArray[right] {
			left = mid + 1
		} else if rotateArray[mid] < rotateArray[right] {
			right = mid
		} else {
			right--
		}
	}

	return rotateArray[left]

}

func minArray(numbers []int) int {
    left := 0
    right := len(numbers) - 1
    for left < right {
        mid := left + (right-left)>>1
        if numbers[mid] > numbers[right] {
            left = mid+1
        }else if numbers[mid] < numbers[right]{
            right = mid
        }else {
            right--
        }
    }
    return numbers[left]
}

4. 参考

• 旋转数组的最小数字_牛客网
• 面试题11. 旋转数组的最小数字（二分法，清晰图解） - 旋转数组的最小数字 - 力扣（LeetCode）