一周刷完剑指offer-6-旋转数组的最小数字

从尾到头打印单链表值

1. 题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

2. 示例

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

3. 解题思路

第一种方法：

这道题是二分查找的变形，注意到旋转数组的首元素肯定不小于旋转数组的尾元素，设置中间点。

如果中间点大于首元素，说明最小数字在后面一半，如果中间点小于尾元素，说明最小数字在前一半。依次循环。

当一次循环中首元素小于尾元素，说明最小值就是首元素。

但是当首元素等于尾元素等于中间值，只能在这个区域顺序查找。如：【1,2,2,3,4】 --> 【2,3,4,1,2】

第二种方法：简单，直接遍历 复杂度较高

4. Java实现

方法一：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int len = array.length;
        if (len == 0){
            return 0;
        }
        
        // 如果第一个数字 都比最后一个数字小，则代表没有旋转
        int left = 0;
        int right = len - 1;
        if (array[left] < array[right]){
            return array[left];
        }
        
        int mid;
        int minVal = array[left];
        while ((right - left) > 1){
            mid = (right + left) / 2;
            if (array[left] <= array[mid]){
                left = mid;
            }else if (array[right] >= array[mid]){
                right = mid;
            }else if ((array[left] == array[mid]) && array[mid] == array[right]){
                // 只能遍历找到最小的值
                for (int i = 0; i < len; i++){
                    if (minVal > array[i]){
                        minVal = array[i];
                        right = i;
                    }
                    
                }
            }
        }
 
        return array[right];
        
    
    }
}

方法二：直接遍历

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        // 直接使用遍历的方法
        if (array.length == 0){
            return 0;
        }
        
        int minVal = array[0];
        for (int i = 0; i < array.length; i++){
            if (minVal > array[i]){
                minVal = array[i];
            }
        }
        return minVal;
    
    }
}

5. Python实现

第一种：

 -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        
        length = len(rotateArray)
        left, right = 0, length-1
        if rotateArray[left] < rotateArray[right]: #如果第一个数都比最后一个数小，则代表没有旋转
            return rotateArray[left]
        
        minVal = rotateArray[0]
        while (right - left) > 1:
            mid = (left + right) // 2
            if rotateArray[mid] >= rotateArray[left]:
                left = mid 
            elif rotateArray[mid] <= rotateArray[right]:
                right = mid 
            elif rotateArray[right] == rotateArray[left] == rotateArray[mid]:
                for i in range(length):
                    if minVal > rotateArray[i]:
                        minVal = rotateArray[i]
                        right = i 
        minVal = rotateArray[right]
        return minVal   

第二种：

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        
        minVal = rotateArray[0]
        for i in range(len(rotateArray)):
            if minVal > rotateArray[i]:
                minVal = rotateArray[i]
                res = i 
        return rotateArray[res] 

如果您觉得本文有用，请点个“在看”