[剑指-06](php&python):旋转数组的最小数字

说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。

题目来源

• 分类：数组
• 旋转数组的最小数字

题目描述

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

解题思路（参考剑指offer 第二版）

• 利用二分查找法的思路，使用两个指针分别指向数组的第一个元素和最后一个元素，接着找到数组中间的元素。如果中间元素位于前面的递增数组中，那么则此元素大于或者等于第一个指针所指向的元素；此时数组中的最小值应该位于该中间指针后面，所以把第一个指针指向该中间元素，从而缩小寻找范围。同样，如果中间元素位于后面的递增子数组中，那它应该小于或者等于第二个指针所指向元素，此时最小元素应该位于该中间中间元素的前面，把第二个指针指向该元素；不管移动第一个指针还是第二个指针，查找范围都会缩小到原来的一半。接下来我们在使用更新之后的两个指针重复做新一轮的查找。
• 根据上面的操作，第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最后第一个指针会指向前面数组的最后的一个元素，第二个指针会指向后面子数组的第一个元素，两个指针为指向两个相邻元素（循环结束的条件），第二个指针刚好是最小元素。

Note:

• 1.数组已经是旋转后的数组；
  针对此情况开始直接判断首元素与最后元素的大小关系
  2.特殊数组[1, 0 , 1, 1, 1]第一个指针，第二个指针，中间指针元素值相等。
  针对此情况，无法判断中间元素是属于前面数组，还是后面的子数组，只能采用顺序查找的方法。

编程实现

PHP

运行时间：727ms

占用内存：5624k
<?php

function minNumberInRotateArray($rotateArray)
    {
        if(count($rotateArray) == 0 || empty($rotateArray)){
            return 0;
        }
        $length = count($rotateArray);
        $left = 0;
        $right = $length - 1;
        //如果是已经旋转后的数组，所以才会有此句,直接进入返回
        $indexMid = $left;
        while ($rotateArray[$left] >= $rotateArray[$right]) {
            
            if($right - $left == 1){
                return $rotateArray[$right];
                break;
            }
            //一定要注意：不使用floor（或者ceil函数）存在问题，php运算符‘/’ 是浮点运算，不是c语言整除
            $indexMid = floor(($left + $right) / 2);
            
            if($rotateArray[$left] == $rotateArray[$right] && $rotateArray[$indexMid] == $rotateArray[$left]){
                return findMin($rotateArray, $left, $right);
            }
            if($rotateArray[$indexMid] >= $rotateArray[$left]){
                $left = $indexMid;
            }elseif ($rotateArray[$indexMid] <= $rotateArray[$right]){
                $right = $indexMid;
            }
        }
        return $rotateArray[$indexMid];
    }
    // 顺序查找
    function finMin($rotateArray, $left, $right){
        $result = $rotateArray[$left];
        $index = $left + 1;
        for($index;$index <= $right; ++$index){
            if($result > $rotateArray[$index]){
                $result = $rotateArray[$index];
            }
        }
        return $result;
    }

/* 测试用例 
a. 功能测试（输入数组为升序数组的一个旋转，存在重复或者不存在重复元素）
b. 边界测试（只包含一个数字的数组）
c.特殊输入测试（数组为空等）
*/
$array = array(4,5,7,9,10,0,1,2,3);
var_dump(minNumberInRotateArray($array));
?>

Python

# -*- coding:utf-8 -*-
class Solution:
    def MinNumber(self, rotateArray, left, right):
        res = rotateArray[left]
        for i in range(left, right + 1):
            if rotateArray[i] < res:
                res = rotateArray[i]
        return res

    def minNumberInRotateArray(self, rotateArray):
        # write code here
        length = len(rotateArray)
        if length == 0:
            return 0
        else:
            left = 0
            right = length - 1
            while left <= right:
                # 不做此处理时间会超时
                if (right - left) == 1:
                    return rotateArray[right]
                mid = (left + right) / 2
                # 如果出现大量重复(例如：[1,0,1,1,1])，只能顺序查找
                if rotateArray[mid] == rotateArray[left] and rotateArray[mid] == rotateArray[right]:
                    return self.MinNumber(rotateArray, left, right)
                elif rotateArray[mid] >= rotateArray[left]:
                    left = mid
                elif rotateArray[mid] <= rotateArray[right]:
                    right = mid
            return rotateArray[right]


s = Solution()
print s.minNumberInRotateArray([1, 0, 1, 1, 1])
print s.minNumberInRotateArray([3, 4, 5, 1, 2])

知识总结复习

• PHP运算符 /
• floor() ceil()
  floor()向下取整，ceil()向上取整