美文网首页
每日一题 [10]-旋转数组的最小数字

每日一题 [10]-旋转数组的最小数字

作者: MAXPUP | 来源:发表于2017-03-02 17:15 被阅读0次

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

    解:这道题本质上是寻找最小值,但关键在于利用旋转数组的特性,我也不懂旋转数组是不是都是从递增数组变得,但是百度和牛客的答案告诉我就是这样,如果是这样的话,就用二分法吧。

    function minNumberInRotateArray(rotateArray)
    {
        if(rotateArray.length === 0) return 0;
        if(rotateArray.length == 1) return rotateArray[0];
        var start = 0;
        var end = rotateArray.length;
        var med;
        while ((end - start) > 1) {
          med = parseInt((end+start)/2)
          console.log('start='+start + 'end' + end + 'med' + med);
    
          if(rotateArray[med]<rotateArray[0]){
            end = med;
          }else {
            start = med;
          }
        }
        return rotateArray[start]<rotateArray[end]?rotateArray[start]:rotateArray[end];
    }
    

    我觉得这是我写的最像答案的一次代码。。。。
    看了一下别人的代码,有的直接利用5大于4且5大于1这个规律找到的,服

    相关文章

      网友评论

          本文标题:每日一题 [10]-旋转数组的最小数字

          本文链接:https://www.haomeiwen.com/subject/zklkgttx.html