题解 | #旋转数组的最小数字#
旋转数组的最小数字
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
import java.util.ArrayList;
public class Solution
{
public int minNumberInRotateArray(int [] array)
{
int l, r;
l = 0;
r = array.length - 1;
while(l < r)
{
int mid = (l + r) / 2;
if(array[mid] > array[r])
{
l = mid + 1;
}
else if(array[mid] == array[r])
{
r = mid;
}
}
return array[l];
}
}
public class Solution
{
public int minNumberInRotateArray(int [] array)
{
int l, r;
l = 0;
r = array.length - 1;
while(l < r)
{
int mid = (l + r) / 2;
if(array[mid] > array[r])
{
l = mid + 1;
}
else if(array[mid] == array[r])
{
// 这里必须要特别注意，当array[mid] == array[r] 的时候，首先确定一点是这种情况下是不清楚旋转点在mid左还是右的，参考[1,2,1,1,1]和[1,0,1,1,1]。所以此时只能l或r挪动一个，一个一个排查，但为什么挪动的不是l而是r呢？首先l我们不确定是否在旋转点上，
// 如果l在旋转点上的话肯定是不能挪动l的，再看r，如果r和mid同一个元素上的话，由于这个元素可能是旋转点，我们依然不能挪动r，但是，因为我们能够确定r和mid一定不是同一个索引，所以在mid和r的元素值相等时，我们一定可以让r挪动。
// 那么为什么我们能够确定mid和r一定不是同一个索引号呢？因为mid = (l + r) / 2这个式子是向下取整的，所以r和mid相等只在一个前提条件下才会成立，就是l==r，如果l不等于r，mid就一定不会和r相等，而我们的while循环保证了在循环内l一定不等于r，所以，
// 在array[mid] == array[r]，我们可以挪动r，也只能挪动r。
r--;
}
else{
r = mid;
}
}
return array[l];
}
}
投递完美世界等公司10个岗位 >
