网站建设与管理中专,服务器多少钱,想招代理去什么网站,吐鲁番市网站建设✨个人主页#xff1a;bit me#x1f447; ✨当前专栏#xff1a;算法训练营#x1f447; 旋 转 数 组 的 最 小 数 字核心考点#xff1a;数组理解#xff0c;二分查找#xff0c;临界条件
描述#xff1a;
有一个长度为 n 的非降序数组#xff0c;比如[1,2,3,4,5]… ✨个人主页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[i1]){return array[i1];}}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;
}在这里我们就进行线性查找依次遍历比较大小即可 中间值和左右端点进行比较直到找到为止
mid (right left) 1;
if(array[mid] array[left]){left mid;
}else{right mid;
}总的代码
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];}
}
