剑指offer-1:旋转数组的最小数字
旋转数组的最小数字
1、题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
2、我的解答:
import java.util.ArrayList;
/*
本题考察重点:分类思想
非减排序即包括递增排序和全等
*/
public class Solution {
public int minNumberInRotateArray(int [] array) {
int count = ;
int result = ;
if(array.length==){
return result;
}
for(int i=;i<array.length-;i++){
if(array[i]>array[i+]){
result = array[i+];
}
if(array[i]==array[i+]){
count++;
}
}
if(count==array.length){
result = array[];
}
return result;
}
}
3、思考:我的解答没有考虑到旋转数组和原数组相同的情况,而且从头开始对数组进行遍历,时间复杂度O(n)。
4、优质解答:
1)内置排序工具
利用 Arrays 工具类里的排序函数,内置实现是三项切分快排,默认的排序规则是从小到大,排序后的数组第一个值就是最小值
代码:
import java.util.*;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int n = array.length;
if(n == ){
return ;
}
Arrays.sort(array);
return array[];
}
}
2)二分查找
a. 注
非递减序列并不能找到最小值,因为对于{3, 3, 3, 3, 3, 1, 3} 和 {3, 1,3, 3, 3, 3, 3},二分法并不能判断范围向哪边收缩
b. 分析
二分查找用于查找有序的数组中的值,题目所给数组在两段范围内有序,我们可以将给定数组分为两种情况:
其实并没有旋转,例如 {1,2,3,4,5},旋转后也是 {1,2,3,4,5},这样可以直接使用二分查找
如题所示,旋转了一部分,例如 {1,2,3,4,5},旋转后为 {3,4,5,1,2},需要限定特殊条件后使用二分查找
当数组如情况 1,有个鲜明的特征,即数组左边元素 < 数组右边元素,这时我们直接返回首元素即可
当数组如情况 2,此时有三种可能找到最小值:
标为 n+1 的值小于下标为 n 的值,则下标为 n+1 的值肯定是最小元素
下标为 n 的值小于下标为 n-1 的值,则下标为 n 的值肯定是最小元素
由于不断查找,数组查找范围内的值已经全为非降序(退化为情况1)
再讨论每次二分查找时范围的变化,由于情况数组的情况 1 能直接找到最小值,需要变化范围的肯定是情况 2:
当下标为 n 的值大于下标为 0 的值,从 0 到 n 这一段肯定是升序,由于是情况 2,最小值肯定在后半段
当下标为 n 的值小于下标为 0 的值,从 0 到 n 这一段不是升序,最小值肯定在这一段
c. 代码
import java.util.*;
public class Solution {
public int minNumberInRotateArray(int [] nums) {
if (nums.length == 1) {
return nums[0];
}
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[l] < nums[r]) {
return nums[l];
}
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
if (nums[mid] < nums[mid - 1]) {
return nums[mid];
}
if (nums[mid] > nums[0]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return 0;
}
}
d. 复杂度
时间复杂度:O(logn)
空间复杂度:O(1)
最新文章
- Prototypes in Javascript 收集.__proto__
- 我需要在Web上完成一个图片上传的功能后续(+1)
- HDU 5734 Acperience (公式推导) 2016杭电多校联合第二场
- MySQL PLSQL Demo - 005.IF THEN ELSEIF THEN ELSE END IF
- Python之格式化输出讲解
- 微信多媒体上传图片,创建卡券上传 LOGO
- WPF中的文字修饰
- JEditorPane中html文档中文乱码解决
- Nginx源码研究三:Epoll在NGINX中的使用
- springboot 1.5.2 thymeleaf 标签未关闭异常解决办法
- C语言-第一次作业
- ogg 单表拆分合并进程
- python判断小数示例&;写入文件内容示例
- day4-list,列表
- apache、nginx的虚拟域名配置和rewrite配置,以及web缓存的几种方式
- android保持服务不休眠(持续运行)以及唤醒屏幕的方法
- WordConuts
- js知识点: 数组
- tornado输入-get_query_argument()等 笔记
- JVM 堆内存和非堆内存