✨个人主页:bit me👇
✨当前专栏:算法训练营👇
核心考点:数组理解,二分查找,临界条件 |
描述:
有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这样一个旋转数组,求数组中的最小值。给出的所有元素都大于0,若数组大小为0,请返回0。
数据范围:
1 ≤ n ≤ 10000,数组中任意元素的值: 0 ≤ val ≤ 10000
要求:
- 空间复杂度:O(1)
- 时间复杂度:O(logn)
示例1:
输入:[3,4,5,1,2]
返回值:1
示例2:
输入:[3,100,200,3]
返回值:3
思路:
- 第一种方法:此题就是寻找最小值,最容易普遍的一种思路就是直接遍历,因为是非递减的,所以最小值可能出现在任何一个地方,但是注意,旋转有种特性,旋转之后,有可能出现递减,那么引起递减的第一个数字肯定就是我们要找的最小值。
- 第二种方法:由于第一种方法效率比较低下,思路也不够新颖,在我们提到查找的时候,就该想到 " 查找的本质是排除 " 这句话。采用二分查找!因为是旋转非递减数组,所以可以把整个数组分为两半,mid 是中间二分的值,left 是最左边的值,right 是最右边的值,当我们的 mid 值大于 left 值的时候,就说明 mid 处于原始数组前半部分,根据非递减的特性,就说明目标最小值在 mid 的右侧,然后让 left = mid 之后继续进行二分查找,直到找到为止;反之,当我们的 mid 值小于 left 值的时候,就说明 mid 处于原始数组后半部分,根据非递减的特性,就说明目标最小值在 mid 的左侧,然后让 right = mid 之后继续进行二分查找,直到找到为止。
- 注意非递减:所以有递增和相等两种可能,分别处理即可
第一种方法:
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array == null || array.length == 0){
return 0;
}
for(int i = 0; i < array.length-1; i++){
if(array[i] > array[i+1]){
return array[i+1];
}
}
return array[0];
}
}
第二种方法:
- 先处理特殊情况,数组为空或者长度为 0 的时候
if(array == null || array.length == 0){
return 0;
}
- 定义左右端点和中间值
int left = 0;
int right = array.length -1;
int mid = 0;
- 二分要循环进行查找,那么就要需要一个条件,条件就是 left < right
while(left < right){
//...
}
- 后续代码在循环中完善,先考虑特殊情况,数组只有一个元素的时候
if(right - left == 1){
mid = right;
break;
}
- 非递减除了递增就还有左右端和中间值三个元素一样的情况
if(array[left] == array[right] && array[mid] == array[left]){
int result = array[left];
for(int i = left + 1; i < right; i++){
if(result > array[i]){
result = array[i];
}
}
return result;
}
在这里我们就进行线性查找,依次遍历比较大小即可文章来源:https://www.toymoban.com/news/detail-418973.html
- 中间值和左右端点进行比较直到找到为止
mid = (right + left) >> 1;
if(array[mid] >= array[left]){
left = mid;
}else{
right = mid;
}
总的代码:文章来源地址https://www.toymoban.com/news/detail-418973.html
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array == null || array.length == 0){
return 0;
}
int left = 0;
int right = array.length -1;
int mid = 0;
while(left < right){
if(right - left == 1){
mid = right;
break;
}
//线性查找
if(array[left] == array[right] && array[mid] == array[left]){
int result = array[left];
for(int i = left + 1; i < right; i++){
if(result > array[i]){
result = array[i];
}
}
return result;
}
mid = (right + left) >> 1;
if(array[mid] >= array[left]){
left = mid;
}else{
right = mid;
}
}
return array[mid];
}
}
到了这里,关于【剑指 offer】旋转数组的最小数字的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!