国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

數據結構與算法（查找和排序） --javascript語言描述

Stardustsky / 616人閱讀

摘要：如此，便可以縮小搜索范圍，提高時間復雜度，最終第一個指針指向前面子數組的最后一個元素，而第二個指針指向后面子數組的第一個元素，它們處于相鄰位置，而第二個指針指向的剛好是最小的元素。

旋轉數組的最小數字（二分查找）

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大于0，若數組大小為0，請返回0。

思路：

1.設置兩個指針，初始狀態第一個指針指向前面子數組的第一個元素，第二個指針指向后面子數組的最后一個元素；

2.找到兩個指針的中間元素；

3.若其大于等于第一個指針指向的元素，則說明其在前面的子數組中，且顯然最小元素在中間元素的右邊，若其小于等于第二個指針指向的元素，則說明其在后面的子數組中，且顯然最小元素在中間元素的左邊。

如此，便可以縮小搜索范圍，提高時間復雜度，最終第一個指針指向前面子數組的最后一個元素，而第二個指針指向后面子數組的第一個元素，它們處于相鄰位置，而第二個指針指向的剛好是最小的元素。

注意：按旋轉規則，第一個元素應該是大于或等于最后一個元素的；但也有特例：若把排序數組的前0個元素搬到最后面，及排序數組本身，仍是數組的一個旋轉，此時數組中的第一個數字是最小的數字。

注意：當兩個指針指向的數字及它們中間的數字三者相等時，無法判斷中間數字位于前面的子數組還是后面的子數組，也就無法移動兩個指針來縮小查找的范圍，此時只能用順序查找的方法。

例如：數組{1,0,1,1,1}和數組{1,1,1,0,1}都可看成是遞增數組{0,1,1,1,1}的旋轉。第一種情況，中間數字位于后面的子數組，第二種情況，中間數字位于前面的子數組。

function minNumberInRotateArray(arr) {
  let index1 = 0;
  let index2 = arr.length - 1;
  let indexMid = index1;
  while(arr[index1] >= arr[index2]) {
    if(index2 - index1 == 1) {
      indexMid = index2;
      break;
    }
    indexMid = Math.floor((index1 + index2 ) / 2);
    //如果下標為index1、index2和indexMid指向的三個數字相等
    //則只能順序查找
    if(arr[index1] == arr[index2] && arr[indexMid] == arr[index1]) {
      return MininOrder(arr,index1,index2);
    }
    if(arr[indexMid] >= arr[index1]) {
      index1 = indexMid;
    }
    if(arr[indexMid] <= arr[index2]) {
      index2 = indexMid;
    }
  }
  return arr[indexMid];
}

//按順序查找函數
function MininOrder(arr,index1,index2) {
  let res = arr[index1];
  for (var i = index1 + 1; i <= index2; i++) {
    if(res > arr[i]) {
      res = arr[i];
    }
  }
  return res;
}

console.log(minNumberInRotateArray([3,4,5,1,2]));

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/107504.html

相關文章

  • 數據結構與算法：二分查找

    摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數據結構 簡單數據結構（必須理解和掌握） 有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間?。?無序數據結構：集合、字典、散列表，無序...

    zsirfs 評論0 收藏0

  • 數據結構與算法：二分查找

    摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數據結構 簡單數據結構（必須理解和掌握） 有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小） 無序數據結構：集合、字典、散列表，無序...

    you_De 評論0 收藏0

  • 數據結構與算法：二分查找

    摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數據結構 簡單數據結構（必須理解和掌握） 有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小） 無序數據結構：集合、字典、散列表，無序...

    gotham 評論0 收藏0

  • 基礎數據結構和算法概念

    摘要：數據結構程序數據結構算法數據結構基本概念數據的邏輯結構反映數據元素之間的關系的數據元素集合的表示。這兩部分信息組成數據元素的存儲映象，稱為結點。 本文涉及更多的是概念，代碼部分請參考之前寫過的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本數據結構和查找算法 本文主要是基礎的數據結構和算法概念，可能部分地方會涉及更高級的算法和算法，具體內容以...

    fsmStudy 評論0 收藏0

  • JavaScript數據結構和算法

    摘要：棧被稱為一種后入先出的數據結構。散列使用的數據結構叫做散列表。這些操作需要求助于其他數據結構，比如下面介紹的二叉查找樹。 前言 在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務器端編程。鑒于JavaScript語言已經走出了瀏覽器，程序員發現他們需要更多傳統語言（比如C++和Java）提供的工具。這些工具包括傳統的數據結構（如鏈表，棧，隊列，圖等），...

    EastWoodYang 評論0 收藏0

  • 【二分查找】| 模擬 20 萬數據快速查詢 IP 歸屬地

    摘要：通過兩個二分查找的條件繼續進行問題的分析，那么問題又來了，二分查找是快速的查找一個數據是否存在一組數據中，而且效率極高，億查找一個數據只需次查找。二分查找的三點重點循環退出條件注意是而不是。 showImg(https://segmentfault.com/img/remote/1460000018761246);這篇文章主要深入數據結構與算法在解決實際問題怎么運用和分析的，對于 IP...

    The question 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<