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];
}
}