美文网首页
每日一题 [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