剑指offer66题--Java实现，c++实现和python实现 9.旋转数组的最小数字

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer66题--Java实现，c++实现和python实现 9.旋转数组的最小数字，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2514字，纯文字阅读大概需要4分钟。

内容图文

题目描述

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

c++实现

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int length=rotateArray.size();
        if(rotateArray.empty()||length<=0)
            return 0;
        int index1=0;
        int index2=length-1;
        int indexMid=index1;
        while(rotateArray[index1]>=rotateArray[index2])
        {
            if(index2-index1==1)
            {
                indexMid=index2;
                break;
            }
            indexMid=(index1+index2)/2;
            //如果下标index1,index2和indexMid相等则使用顺序查找
            if(rotateArray[index2]==rotateArray[index1]&&
              rotateArray[indexMid]==rotateArray[index1])
                return MininOrder(rotateArray,index1,index2);
            if(rotateArray[indexMid]>=rotateArray[index1])
                index1=indexMid;
            else if(rotateArray[indexMid]<=rotateArray[index2])
                index2=indexMid;
        }
        return rotateArray[indexMid];
    }
    int MininOrder(vector<int> rotateArray,int index1,int index2)
    {
        int result=rotateArray[index1];
        for(int i=index1+1;i<=index2;++i)
        {
            if(result>rotateArray[i])
            {
                result=rotateArray[i];
            }
        }
        return result;
    }
};

Java实现

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int length=array.length;
        if(length<=0)
            return 0;
        int index1=0;
        int index2=length-1;
        int indexMid=index1;
        while(array[index1]>=array[index2])
        {
            if(index2-index1==1)
            {
                indexMid=index2;
                break;
            }
            indexMid=(index1+index2)/2;
            //如果下标index1,index2和indexMid相等则使用顺序查找
            if(array[index2]==array[index1]&&
              array[indexMid]==array[index1])
                return MininOrder(array,index1,index2);
            if(array[indexMid]>=array[index1])
                index1=indexMid;
            else if(array[indexMid]<=array[index2])
                index2=indexMid;
        }
        return array[indexMid];
    }
            int MininOrder(int [] array,int index1,int index2)
        {
            int result=array[index1];
            for(int i=index1+1;i<=index2;++i)
            {
                if(result>array[i])
                {
                    result=array[i];
                }
            }
            return result;
        }
}

python实现

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        lenArr = len(rotateArray)
        left, right = 0, lenArr-1
        while left <= right:
            if right - left == 1:
                return rotateArray[right]
            mid = (left + right)//2
            if rotateArray[mid] == rotateArray[right]:
                return self.MinInOrder(rotateArray, left, right)
            if rotateArray[mid] >= rotateArray[left]:
                left = mid
            elif rotateArray[mid] <= rotateArray[right]:
                right = mid
        return rotateArray[right]
    def MinInOrder(self, rotateArray, left, right):
        res = rotateArray[left]
        for i in range(left, right+1):
            if res > rotateArray[i]:
                res = rotateArray[i]
        return res

内容总结

以上是互联网集市为您收集整理的剑指offer66题--Java实现，c++实现和python实现 9.旋转数组的最小数字全部内容，希望文章能够帮你解决剑指offer66题--Java实现，c++实现和python实现 9.旋转数组的最小数字所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端