说明：记录刷剑指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()向上取整
网友评论