剑指offer【06】- 旋转数组的最小数字(java)

题目:旋转数组的最小数字

考点:查找和排序

题目描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

法一:利用Arrays.sort()排序

 import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public int minNumberInRotateArray(int [] array) {
//数组为空时
if(array.length == ){
return ;
}
//升序排序
Arrays.sort(array);
return array[];
}
}

法二:分情况讨论

1.数组为空
2.部分旋转,例如由(1,2,3,4,5)旋转为(3,4,5,1,2),此时只需要遍历数组,找到当前数比前面的数小的数即可。
3.完全旋转,例如由(1,2,3,4,5)旋转为(1,2,3,4,5),此时第一个数最小。
 import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public int minNumberInRotateArray(int [] array) {
//数组为空时
if(array.length == ){
return ;
}
if(array.length == ){
return array[];
}
//前部分数据旋转
for(int i = ; i < array.length - ; i++){
if(array[i] > array[i+]){
return array[i+];
}
}
//全部数据旋转,相当于没有旋转
return array[];
}
}

法三:二分法

 import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if (array.length == ){
return ;
}
int left = ;
int right = array.length - ;
int middle = ;
while (array[left]>=array[right]) {
//数组长度等于2时
if(right-left==){
middle = right;
break;
}
middle = left + (right - left) / ;
if (array[middle] >= array[left]) {
left = middle;
}
if (array[middle] <= array[right]) {
right = middle;
}
}
return array[middle];
}
}
上一篇:QuestaSim自动化仿真之do文件


下一篇:CVE-2020-0796—远程代码执行漏洞