精品国产人成在线_亚洲高清无码在线观看_国产在线视频国产永久2021_国产AV综合第一页一个的一区免费影院黑人_最近中文字幕MV高清在线视频

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

C語言:LeetCode 153尋找旋轉排序數組中的最小值

如意 ? 來源:CSDN ? 作者:CaspianSea ? 2020-06-22 08:59 ? 次閱讀

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

( 例如,數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。

請找出其中最小的元素。

你可以假設數組中不存在重復元素。

示例 1:

輸入: [3,4,5,1,2]

輸出: 1

示例 2:

輸入: [4,5,6,7,0,1,2]

輸出: 0

這道尋找最小值的題目可以用二分查找法來解決,時間復雜度為O(logN),空間復雜度為O(1)。

看一下代碼:

C語言:LeetCode 153尋找旋轉排序數組中的最小值

首先說一下主要思路:

單調遞增的序列:

*

*
*

*

*

做了旋轉:

*

*

*

*

*

用二分法查找,需要始終將目標值(這里是最小值)套住,并不斷收縮左邊界或右邊界。

左、中、右三個位置的值相比較,有以下幾種情況:

左值 《 中值, 中值 《 右值 :沒有旋轉,最小值在最左邊,可以收縮右邊界

左值 》 中值, 中值 《 右值 :有旋轉,最小值在左半邊,可以收縮右邊界

左值 《 中值, 中值 》 右值 :有旋轉,最小值在右半邊,可以收縮左邊界

左值 》 中值, 中值 》 右值 :單調遞減,不可能出現

分析前面三種可能的情況,會發現情況1、2是一類,情況3是另一類。

如果中值 《 右值,則最小值在左半邊,可以收縮右邊界。

如果中值 》 右值,則最小值在右半邊,可以收縮左邊界。

通過比較中值與右值,可以確定最小值的位置范圍,從而決定邊界收縮的方向。

而情況1與情況3都是左值 《 中值,但是最小值位置范圍卻不同,這說明,如果只比較左值與中值,不能確定最小值的位置范圍。

所以我們需要通過比較中值與右值來確定最小值的位置范圍,進而確定邊界收縮的方向。

接著分析解法里的一些問題:

首先是while循環里的細節問題。

這里的循環不變式是left 《 right, 并且要保證左閉右開區間里面始終套住最小值。

中間位置的計算:mid = left + (right - left) / 2

這里整數除法是向下取整的地板除,mid更靠近left,

再結合while循環的條件left 《 right,

可以知道left 《= mid,mid 《 right,

即在while循環內,mid始終小于right。

因此在while循環內,nums[mid]要么大于要么小于nums[right],不會等于。

這樣else {right = mid;}這句判斷可以改為更精確的

else if (nums[mid] 《 nums[right]) {right = mid;}。

再分析一下while循環退出的條件。

如果輸入數組只有一個數,左右邊界位置重合,left == right,不會進入while循環,直接輸出。

如果輸入數組多于一個數,循環到最后,會只剩兩個數,nums[left] == nums[mid],以及nums[right],這里的位置left == mid == right - 1。

如果nums[left] == nums[mid] 》 nums[right],則左邊大、右邊小,

需要執行left = mid + 1,使得left == right,左右邊界位置重合,循環結束,nums[left]與nums[right]都保存了最小值。

如果nums[left] == nums[mid] 《 nums[right],則左邊小、右邊大,

會執行right = mid,使得left == right,左右邊界位置重合,循環結束,nums[left]、nums[mid]、nums[right]都保存了最小值。

細化了的代碼:

C語言:LeetCode 153尋找旋轉排序數組中的最小值

再討論一個問題:

為什么左右不對稱?為什么比較mid與right而不比較mid與left?能不能通過比較mid與left來解決問題?

左右不對稱的原因是:

這是循環前升序排列的數,左邊的數小,右邊的數大,而且我們要找的是最小值,肯定是偏向左找,所以左右不對稱了。

為什么比較mid與right而不比較mid與left?

具體原因前面已經分析過了,簡單講就是因為我們找最小值,要偏向左找,目標值右邊的情況會比較簡單,容易區分,所以比較mid與right而不比較mid與left。

那么能不能通過比較mid與left來解決問題?

能,轉換思路,不直接找最小值,而是先找最大值,最大值偏右,可以通過比較mid與left來找到最大值,最大值向右移動一位就是最小值了(需要考慮最大值在最右邊的情況,右移一位后對數組長度取余)。

以下是先找最大值的代碼,可以與前面找最小值的比較:

C語言:LeetCode 153尋找旋轉排序數組中的最小值

使用left 《 right作while循環條件可以很方便推廣到數組中有重復元素的情況,即154題:

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

只需要在nums[mid] == nums[right]時挪動右邊界就行:

初始條件是左閉右閉區間,right = nums.size() - 1,

那么能否將while循環的條件也選為左閉右閉區間left 《= right?

可以的,代碼如下:

C語言:LeetCode 153尋找旋轉排序數組中的最小值

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • C語言
    +關注

    關注

    180

    文章

    7598

    瀏覽量

    136188
  • leetcode
    +關注

    關注

    0

    文章

    20

    瀏覽量

    2311
收藏 人收藏

    評論

    相關推薦

    幫忙看看:數字排序數組

    如何按照圖中數字排序數組簇~~謝謝
    發表于 06-12 10:45

    數組的最大最小值模塊輸出端的含義

    各位大神,那個最大索引,最小索引是什么意思?如果數組是一位數組,索引出來的是最大最小值的位置?
    發表于 04-22 09:46

    labview數組全是負數最大最小值顯示不對

    labview數組全是負數最大最小值就會變反怎么回事,(最大變成最小值最小值變成最大
    發表于 06-27 14:43

    一維數組找出最小值及它的位置索引,其實如果只是這樣還好,但它要所有索引位置(如果有多個最小值

    查找一個一維數組最小值,以及最小值數組的位置索引,如果有多個最小值,找到所有
    發表于 10-19 17:12

    C語言教程之查找數組的最

    C語言教程之查找數組的最,很好的C語言資料,快來
    發表于 04-25 15:13 ?0次下載

    C語言教程之求數組元素最小值

    C語言教程之求數組元素最小值,很好的C語言資料,
    發表于 04-25 16:09 ?0次下載

    C語言教程之對數組進行升序和降序排序

    C語言教程之對數組進行升序和降序排序,很好的C語言資料,快來學習吧。
    發表于 04-25 16:09 ?0次下載

    排除最大最小值后求平均值

    輸入數據中排除最大最小值后求平均值的算法,測試通過。
    發表于 08-18 18:24 ?11次下載

    C語言leetcode 35搜索插入位置

    給定一個排序數組和一個目標值,在數組中找到目標值,并返回其索引。如果目標值不存在于數組,返回它將會被按順序插入的位置。
    的頭像 發表于 06-22 08:40 ?1618次閱讀
    <b class='flag-5'>C</b><b class='flag-5'>語言</b>:<b class='flag-5'>leetcode</b> 35搜索插入位置

    C語言: Leetcode 33搜索旋轉排序數組

    假設按照升序排序數組在預先未知的某個點上進行了旋轉
    的頭像 發表于 06-22 08:51 ?1685次閱讀
    <b class='flag-5'>C</b><b class='flag-5'>語言</b>: <b class='flag-5'>Leetcode</b> 33搜索<b class='flag-5'>旋轉</b><b class='flag-5'>排序數組</b>

    AD629A SPICE宏模型最小值

    AD629A SPICE宏模型最小值
    發表于 04-13 20:53 ?12次下載
    AD629A SPICE宏模型<b class='flag-5'>最小值</b>

    AD629A SPICE宏模型最小值

    AD629A SPICE宏模型最小值
    發表于 06-17 11:32 ?1次下載
    AD629A SPICE宏模型<b class='flag-5'>最小值</b>

    C語言總結_數組全方位練習

    C語言數組的練習題:涉及到數組插入、數組刪除、數組下標數據的左移右移、
    的頭像 發表于 08-14 09:34 ?866次閱讀

    C語言_數組的查找、替換、排序、拼接

    這篇文章主要是總結C語言的位運算幾個實戰例子,接著介紹數組的基本定義用法、數組排序、插入、拼接、刪除、字符串查找替換等。
    的頭像 發表于 08-14 09:48 ?2525次閱讀

    C 語言數組的基本結構

    數組是最基本的數據結構,關于數組的面試題也屢見不鮮,本文羅列了一些常見的面試題,僅供參考。目前有以下18道題目。 數組求和 求數組的最大
    的頭像 發表于 06-22 10:56 ?575次閱讀