@chyoo1991
2015-09-07T01:19:41.000000Z
字数 1512
阅读 1189
coding
旋转数组
见书66页。
O(logN)
的算法核心观点在于把旋转数组看成两个递增子数组,运用二分查找算法实现。先考虑没有重复数字的情况,再考虑有重复的情况。
public class RolateArray {
public static int getMinNum(int[] numbs) throws Exception{
if(numbs == null || numbs.length == 0) throw new Exception("Invaid array!");
int start = 0;
int end = numbs.length - 1;
int resultIndex = start; // 返回结果的下标默认为start,处理旋转度为0的情况
while(numbs[start] >= numbs[end]) { //如果不满足这个条件,则原数组的旋转度为0
if(end - start == 1) { // start 一定在左边子序列中,end一定在右子序列中
resultIndex = end;
break;
}
int mid = (start + end) / 2;
if(numbs[mid] >= numbs[start]) //在左子序列
start = mid;
else if(numbs[mid] <= numbs[end]) // 在右子序列
end = mid;
}
return numbs[resultIndex];
}
public static void main(String[] args){
int[] a1 = {3, 4, 5, 1, 2, 3}; // 可以求出来
int[] a2 = {3, 3, 3, 1, 2, 3}; // 可以得到正确答案
int[] a3 = {3, 4, 5, 1, 1, 2};
try{
System.out.println(getMinNum(a1));
System.out.println(getMinNum(a2));
System.out.println(getMinNum(a3));
}catch(Exception e){
System.out.println(e);
}
}
}
这个代码的问题在于有时候会因为重复数字而分错了组。当mid/start/end对应的值都相同的时候,这时候无法判断该往哪边移动。此时只能遍历了。
public class RolateArray{
public static int getMinNum(int[] numbs) throws Exception {
if(numbs == null || numbs.length == 0) throw new Exception("Invalid array!");
int start = 0;
int end = numbs.length - 1;
int resultIndex = start;
while(numbs[start] >= numbs[end]) {
if(end - start == 1) {
resultIndex = end;
break;
}
int mid = (start + end) / 2;
if(numbs[start] == numbs[end] && numbs[start] == numbs[mid]){
int tmp = numbs[start];
// 循环找出最小值
for(int i = start + 1; i <= end; i++){
if(numbs[i] < tmp)
tmp = numbs[i];
}
return tmp;
}
else if(numbs[start] <= numbs[mid])
//在左子序列中
start = mid;
else if(numbs[end] >= numbs[mid])
//在右子序列中
end = mid
}
return numbs[resultIndex];
}
}