求解旋轉數組的最小數字。本站提示廣大學習愛好者：（求解旋轉數組的最小數字）文章只能為提供參考，不一定能成為您想要的結果。以下是求解旋轉數組的最小數字正文

求解旋轉數組的最小數字

投稿：lqh

求解旋轉數組的最小數字

題目描述：

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小數組。例如數組{3,4,5,1,2}是數組{1,2,3,4,5}的旋轉數組，該數組的最小值為1。

思路解析：

O(N)的算法

這種算法的思想就是遍歷這個數組，由於這個數組是兩部分有序的數組，因此遍歷這個數組時當後一個數字小於前一個數字時，則後一個（即較小）一定為整個數組中最小的數字。

這種算法的思想很簡單，但就是時間復雜度較大，因此不是很好的算法。

int minNumberInRotateArray(vector<int> rotateArray)
{
  if (rotateArray.empty())
    return -1;

  unsigned int i=0;
  for (; i<rotateArray.size()-1; i++)
  {
    if (rotateArray[i] > rotateArray[i+1])
      break;
  }
  return rotateArray[i+1];
}

O(logN)的算法

這種算法思想類似於二分查找，首先每次找到數組中中間的數字mid，如果mid大於最左端left，說明最小數在mid的右側區間，則改變left，置left為mid；如果mid小於數組右側right，說明最小數在mid的左側區間，則改變right為mid….當left的數字小於等於right的數字時，說明已經找到最小數，這個也是循環結束的條件

int minNumberInRotateArray(vector<int> rotateArray)
{
  if (rotateArray.empty())
    return -1;
  unsigned int left=0;
  unsigned int right=rotateArray.size()-1;
  unsigned int mid=left;
  while (rotateArray[left] >= rotateArray[right])
  {
    if (right-left == 1)
    {
      mid = right;
      break;
    }
    mid = left+((right-left)>>1);

    if (rotateArray[mid]==rotateArray[left] && rotateArray[right]==rotateArray[mid])
      return rotateArray[mid];

    if (rotateArray[mid] >= rotateArray[left])
      left = mid;
    else if (rotateArray[mid] <= rotateArray[right])
      right = mid;
  }
  return rotateArray[mid];
}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！