Java获取旋转数组的最小数字

x33g5p2x  于2021-03-13 发布在 Java  
字(3.2k)|赞(0)|评价(0)|浏览(192)

1. 寻找旋转排序数组中的最小值 I

假设一个旋转排序的数组其起始位置是未知的(比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2)。

你需要找到其中最小的元素。

你可以假设数组中不存在重复的元素。

样例

给出[4,5,6,7,0,1,2] 返回 0

规则
输入:int a[] 一个有序数组旋转后的数组
输出:int 最小的值
case:

数组为null
数组大小为0
数组旋转不变 [0,1,2,3,4,5,6]
数组旋转 [6,0,1,2,3,4,5]
数组旋转 [1,2,3,4,5,6,0]
数组旋转 [2,3,4,5,6,0,1]
数组旋转 [4,5,6,0,1,2,3]

思路

最简单的思路当然是遍历一下,复杂度为O(n)和O(1)
也可以使用一次堆排序,复杂度为O(logn)和O(1)
由于是部分有序的,可以考虑使用二分法,复杂度为O(logn)和O(1)

[0,1,2,3,4,5,6] 旋转后的序列在[0,1,2,3,4,5,6,0,1,2,3,4,5,6] 从里面取相应的长度的数即可,从里面可以看到,最小值0的位置,旋转初期在右侧,最后在左侧,可以选取mid与begin和end对比,例如

[1,2,3,4,5,6,0]  begin=1 mid=4 end=0 当mid>end时说明最小值在右侧
[5,6,0,1,2,3,4]  begin=5 mid=1 end=4 当mid<begin时说明最小值在左侧

这样,我们可以使用二分法进行对比,需要注意的是:begin、mid和end的值如何设置,特别是边界条件[0] [0,1]这种少于三个数据的情况,还有mid=min的情况。
我们可以设置只有两个的时候就停止,因为最小数据必然在这两个里面。而大于两个时,如[2,0,1],mid<begin,在左侧,这时应该从区间[0,2] -> [begin,mid] = [2,0] 在这里面寻找。这时因为,未旋转的数组是有序的,单调递增,而旋转过后,只有不与原来的数组相同,那么一定是递减的。因此如果出现单调递减的,就说明最小值在这个范围内。

代码

public class Solution {
    /*
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int a[]) {
		if(a == null || a.length == 0) return -1; // 异常条件
		int len = a.length;
		if(a[0] < a[len-1]) { // 特殊情况,相当于没有旋转
			return a[0];
		}
		return search(a,0,len-1); // 初始范围
	}
	private int search(int a[],int begin,int end) {
		if(begin == end) return a[begin]; // 如果只有一个数
		if(begin+1 == end) return Math.min(a[begin], a[end]); // 如果只有两个数
		int mid = begin + (end - begin) / 2;  // 计算mid
		if(a[begin] > a[mid]) {  // 左边
			return search(a,begin,mid);
		}else if(a[mid] > a[end]) {  // 右边
			return search(a,mid,end);
		}
		return -1;
	}
}

上面的实现使用了递归,势必造成需要一定的栈空间,可以改造成循环

public class Solution {
    /*
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int a[]) {
		if(a == null || a.length == 0) return -1;
		int len = a.length;
		if(a[0] < a[len-1]) {
			return a[0];
		}
		int begin = 0 , end = a.length - 1;
		while(true) { // 循环
			if(begin == end) return a[begin];
			if(begin+1 == end) return Math.min(a[begin], a[end]);
			int mid = begin + (end - begin) / 2;
			if(a[begin] > a[mid]) {
				end = mid; 
			}else if(a[mid] > a[end]) {
				begin = mid;
			}
		}
	
	}

}

使用一次堆排序的程序

package com.shisj.study.offer.chapter1.revertnum;

/**
 * 使用堆排序
 * @author shisj
 *
 */
public class SearchSmallest0 {

	public int findMin(int a[]) {
		if(a == null || a.length == 0) return -1;
		int len = a.length;
		int begin = (len-2)/2;
		while(begin >=0) {
			swap(a,begin,begin*2+1);
			swap(a,begin,begin*2+2);
			begin --;
		}
		return a[0];
	}
	private void swap(int a[],int parent,int child) {
		if(child > a.length-1)return;
		if(a[parent] > a[child]) {
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;
		}
	}
}

2. 寻找旋转排序数组中的最小值 II

假设一个旋转排序的数组其起始位置是未知的(比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2)。

你需要找到其中最小的元素。

数组中可能存在重复的元素。

样例:
给出[4,4,5,6,7,0,1,2] 返回 0

规则
输入:int a[] 一个有序数组旋转后的数组
输出:int 最小的值
case:

数组为null
数组大小为0
数组旋转不变 [0,0,0,0,1,1,2,3,4,6]
数组旋转 [0,0,1,1,2,3,4,6,0,0]
数组旋转 [1,1,2,3,4,6,0,0,0,0]
数组旋转 [3,4,6,0,0,0,0,1,1,2]

思路

这次加入了重复元素,首先要判断是否可以使用二分法,通过分析,在上一个题目的基础上增加了相等的情形,如[1,1,1,-1,1] 这次,mid=1 begin=1 end=1 只能两个都查找,然后比较大小了。
使用一次堆排序的话不收影响。

规则

public class Solution {
    /*
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int a[]) {
		if(a == null || a.length == 0) return -1;
		int len = a.length;
		if(a[0] < a[len-1]) {
			return a[0];
		}
		return search(a,0,len-1);
	}
	private int search(int a[],int begin,int end) {
		if(begin == end) return a[begin];
		if(begin+1 == end) return Math.min(a[begin], a[end]);
		int mid = begin + (end - begin) / 2;
		if(a[begin] > a[mid]) {
			return search(a,begin,mid);
		}else if(a[mid] > a[end]) {
			return search(a,mid,end);
		}else{
		    int ax =  search(a,begin,mid);
		    int bx =  search(a,mid+1,end);
		    return Math.min(ax,bx);
		}
	}
}

相关文章

微信公众号

最新文章

更多