旋转数组的最小数字

旋转数组的最小数字

题目描述

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

特殊输入{1, 2, 3, 4, 5}; {1, 1, 1, 0, 1}; {1, 0, 1, 1, 1}-->这时版本二, 三只能暴力查找了, 看看版本三med如何初始化

版本一: 从头到尾遍历数组找出最小值, 没什么技术含量,

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int ret = 0;
        int len = rotateArray.size();
        
        if (0 == len) {
            ret = 0;
        }
        else {
            for (int i = 0; i < len; i++) {
                if (rotateArray[i] > rotateArray[i+1]) {
                    ret = rotateArray[i+1];
                    break;
                }
            }
        }
        
        return ret;
    }
};

版本二: 递归版, vt[middle]和vt[start]之间用>还是>=是个疑问

class Solution {
public:
        int min(vector<int> vt) {
            int ret = 0;
            int len = vt.size();
            for (int i = 0; i < len; i++) {
                if (vt[i] > vt[i+1]) {
                    ret = vt[i+1];
                    break;
                }
            }
            
            return ret;
    }
    
    int find(vector<int> vt, int start, int end) {
        int ret;
        int middle = 0;
        
        middle = (start + end) / 2;
        
        if (start+1 == end) {
            
			//不需要这么判断, start永远指向最小值的前面元素
            //return vt[start] < vt[end] ? vt[start] : vt[end];	
			return vt[end];
        }
        
        
        if (vt[middle] == vt[start] == vt[middle] == vt[end]) {
            ret = min(vt);
        }
		// 这么判断牛客上输出结果在下图
        //else if (vt[middle] > vt[start]) {		
        else if (vt[middle] >= vt[start]) {
            start = middle;
            ret = find(vt, start, end);
        }
        else if (vt[middle] <= vt[start]) {
            end = middle;
            ret = find(vt, start, end);
        }
        
        return ret;
    }
    
    int minNumberInRotateArray(vector<int> rotateArray) {
        int ret = 0;
        int len = rotateArray.size();
        
        if (0 == len) {
            ret = 0;
        }
        else if (1 == len) {
            ret = 1;
        }
        else {
            ret = find(rotateArray, 0, len - 1);
        }
        
        return ret;
    }
};

版本四: 非递归版二分法查找, ret初始化为数组第一个结点, 使用while(rotateArray[start] >= rotateArray[end])这么判断, 当数组为有序时, 直接返回最小值

class Solution {
public:
        int min(vector<int> vt) {
            int ret = 0;
            int len = vt.size();
            for (int i = 0; i < len; i++) {
                if (vt[i] > vt[i+1]) {
                    ret = vt[i+1];
                    break;
                }
            }
            
            return ret;
    }
    
    int minNumberInRotateArray(vector<int> rotateArray) {
        int ret = 0;
        int start = 0;
        int end = 0;
        int med = start;
        
        if (0 == rotateArray.size()) {
            return ret;
        }
        
        end = rotateArray.size() - 1;
		ret = rotateArray[start];
        //while(1 != (end - start)) {
		while(rotateArray[start] >= rotateArray[end]) {

            if (rotateArray[start] == rotateArray[med] == rotateArray[end]) {
                ret = min(rotateArray);
                break;
            }
            
			med = (start + end) / 2;
            if (rotateArray[med] >= rotateArray[start]) {
                start = med;
            }
            else if ((rotateArray[med] <= rotateArray[end])) {
                end = med;
            }
			ret = rotateArray[end];        
		}
        
        return ret;
    }
};