剑指Offer的学习笔记（C#篇）-- 旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
一 . 方法分析（正常单调递增数组）
1 . 参考二分查找法，我们用两个指针分别指向数组的第一个元素和最后一个元素。
2 . 基于二分查找法的概念，找到数组中间的元素：因为该题目是查找旋转数组中的最小值。
如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素，这样可以缩小寻找的范围。移动之后的第一个指针仍然位于前面的递增子数组之中。
如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。
3 . 接下来我们再用更新之后的两个指针，重复做新一轮的查找。
可参考下例：
1. 确定Pmid为5，Pmid>P1且Pmid>P2，说明P1到Pmid为单增。
2. 把Pmid定义为P1，新的Pmid为1，这时候Pmid<P1且Pmid<P2，说明Pmid到 P2是单增，把新的Pmid定义为P2。
3. 这时候P1>P2，且位置相差为1，结束，得出最小数为P2。
二 . 特殊条件
1 . 鲁棒判断：即数组长度为0或者为空数组时，应返回0.
2 . 存在相等的数。
例：
1. 有重复数字，并且重复的数字刚好的最小的数字。 { 3, 4, 5, 1, 1, 2 }
2. 有重复数字，但重复的数字不是第一个数字和最后一个数字。 { 3, 4, 5, 1, 2, 2 }
3. 单调升序数组，旋转0个元素，也就是单调升序数组本身。{ 1, 0, 1, 1, 1 }
4. 数组中只有一个数字。{ 1 }
适当的采用顺序查找法。太晚了，明天写吧！！
三 . 代码实现
class Solution { public int minNumberInRotateArray(int[] rotateArray) { // write code here //鲁棒判断 if(rotateArray == null || rotateArray.Length <= 0) { return 0; } //定义三个参数，用于后期的指针 int a = 0; int b = rotateArray.Length - 1; int mid = 0; //while终止条件（每次前者大于后者的时候均要对比，当二者差一个数据位时终止返回） while(rotateArray[a]>=rotateArray[b]) { if(b - a == 1) { mid = b; break; } //二分查找法，对mid参数的修改 mid = (b+a)/2; //特殊情况，特殊对待（即数列中存在相等参数时，就采用顺序查找法） if(rotateArray[a] == rotateArray[mid] && rotateArray[mid] == rotateArray[b]) { int min = rotateArray[a]; for(int i = 0;i<rotateArray.Length-1;i++) { if(min<rotateArray[i]) { min = rotateArray[i]; } } } //二分查找法，前后指针的修改 if(rotateArray[mid]>=rotateArray[a]) { a = mid; } if(rotateArray[mid]<=rotateArray[b]) { b = mid; } } //返回最小值 return rotateArray[mid]; } }
携程开奖24人在聊
投递滴滴等公司8个岗位 >