lintcode:寻找旋转排序数组中的最小值 II
2024-10-04 19:09:56
寻找旋转排序数组中的最小值 II
假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。
你需要找到其中最小的元素。
数组中可能存在重复的元素。
解题
暴力直接线性查找
或者，线性找到第一个开始降序的位置对应的数
应该考虑二分法
递归 + 二分
public class Solution {
/**
* @param num: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] num) {
// write your code here
if( num == null || num.length == 0)
return 0;
if(num.length == 1)
return num[0];
return findMin(num,0,num.length - 1);
}
public int findMin(int[] num,int left,int right){
if(left == right)
return num[left];
if(right == left + 1)
return Math.min(num[left],num[right]);
int mid = (left + right)/2;
if( num[right] > num[left])
return num[left];
else if( num[right] == num [left])
return findMin(num,left + 1,right);
else if(num[mid] >= num[left])
return findMin(num,mid,right);
else
return findMin(num,left,mid);
}
}
Java Code
二分
public class Solution {
/**
* @param num: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] num) {
// write your code here
if( num == null || num.length == 0)
return 0;
if(num.length == 1)
return num[0];
int low = 0;
int high = num.length -1;
int mid = low;
while(low < high){
mid = (low + high)/2;
if(num[mid] > num[high]){
low = mid + 1;
}else if( num[mid] < num[high]){
high = mid ;
}else{
high--;
}
}
return num[low];
}
}
Java Code
最新文章
- Android之SharedPreferences数据存储
- WebView网页中使用到支付宝调不起来，提示ERR_UNKNOWN_URL_SCHEME
- JAVA设计模式《二》
- OC点语法和变量作用域
- nginx 多站点配置方法集合（转）
- React编写文本评论框
- HW7.3
- phpwind9.0 顶部和底部版权信息永久性修改
- 杭电ACM求平均成绩
- Python用subprocess的Popen来调用系统命令
- hdu1041
- digitalocean vpn安装配置教程
- CRUL学习记录
- Web版需求征集系统所得2，servlet中request.getParameter获值乱码问题解决
- HDU 1556 BIT区间修改+单点查询(fread读入优化)
- Badboy教程
- win静态库动态库
- Problem E. Matrix from Arrays（杭电2018年多校第四场+思维+打表找循环节）
- Python函数的初识
- java:RandomAccessFile随机读取文件内容