• 00006.旋转数组的最小数字
  • 发布于 1个月前
  • 46 热度
    0 评论

题目描述:


把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组 {3,4,5,1,2} 为{1,2,3,4,5}的一个旋转,该数组的最小值为 1。 NOTE:给出的所有元素都大于 0,若数组大小为 0,请返回 0。

解题思路:

第一反应:擂台法。从第二个数开始相邻比较。缺点:慢。O(n)。

 public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(0 == array.length) {
            return 0;
        }
        //假设第一个是最小的
        int result = array[0];
        for(int i = 1; i < array.length; i++) {
            //进行比较
            if(result > array[i]) {
                result = array[i];
            }
        }
        return result;
    }
}
第二反应:O(n)的时间效率和O(1)的空间效率。必须优化。思路二分。二分的条件:确保其是个反转数组。所以left必定大于right元素。特殊值考虑:

1. 当剩下最后两个元素的时候,mid元素下标值编程 1 / 2 == 0了。这不对。此时left == 0, right == 1,所以考虑特殊值。

2. 当array[left] == array[mid] == array[right];的时候就无法进行二分。所以此时只能用第一反应中的擂台法来解决。

3. 边界值处理:当数组为null或者元素个数为0的时候。

用图表示为:


代码表示:

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(0 == array.length) {
            return 0;
        }
        int left = 0; 
        int right = array.length - 1;
        int mid = 0;
        while(array[left] >= array[right]) { //确保反转的
            //剩下两个的时候
            if(1 == right - left) {
                mid = right;
                break;
            }
            //无法确定的时候。擂台法。
            if(array[left] == array[mid]&& array[mid]  == array[right]) {
                return LeiTai(array);
            }
            mid = (left + right) / 2;
            if(array[mid] <= array[right]) { //那个值在前半边。
                right = mid;
            } else {
                left = mid; //那个值在后半边。
            }
        }
        return array[mid];
    }
    private int LeiTai(int [] array) {
        int num = array[0];
        for(int i = 1; i < array.length; i++) {
            if(array[i] < num) {
                num = array[i];
            }
        }
        return num;
    }
    
}


用户评论