求解旋轉(zhuǎn)數(shù)組的最小數(shù)字

在珠暉等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專(zhuān)注、極致的服務(wù)理念，為客戶(hù)提供成都網(wǎng)站建設(shè)、網(wǎng)站制作 網(wǎng)站設(shè)計(jì)制作定制制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站制作,全網(wǎng)整合營(yíng)銷(xiāo)推廣,外貿(mào)網(wǎng)站制作,珠暉網(wǎng)站建設(shè)費(fèi)用合理。

題目描述：

把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱(chēng)之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小數(shù)組。例如數(shù)組{3,4,5,1,2}是數(shù)組{1,2,3,4,5}的旋轉(zhuǎn)數(shù)組，該數(shù)組的最小值為1。

思路解析：

O(N)的算法

這種算法的思想就是遍歷這個(gè)數(shù)組，由于這個(gè)數(shù)組是兩部分有序的數(shù)組，因此遍歷這個(gè)數(shù)組時(shí)當(dāng)后一個(gè)數(shù)字小于前一個(gè)數(shù)字時(shí)，則后一個(gè)（即較?。┮欢檎麄€(gè)數(shù)組中最小的數(shù)字。

這種算法的思想很簡(jiǎn)單，但就是時(shí)間復(fù)雜度較大，因此不是很好的算法。

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)的算法

這種算法思想類(lèi)似于二分查找，首先每次找到數(shù)組中中間的數(shù)字mid，如果mid大于最左端left，說(shuō)明最小數(shù)在mid的右側(cè)區(qū)間，則改變left，置left為mid；如果mid小于數(shù)組右側(cè)right，說(shuō)明最小數(shù)在mid的左側(cè)區(qū)間，則改變r(jià)ight為mid….當(dāng)left的數(shù)字小于等于right的數(shù)字時(shí)，說(shuō)明已經(jīng)找到最小數(shù)，這個(gè)也是循環(huán)結(jié)束的條件

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];
}

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

當(dāng)前題目：求解旋轉(zhuǎn)數(shù)組的最小數(shù)字
本文鏈接：http://jinyejixie.com/article2/ppshoc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開(kāi)發(fā)、商城網(wǎng)站、小程序開(kāi)發(fā)、自適應(yīng)網(wǎng)站、網(wǎng)站收錄、品牌網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)