• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • LeetCode153 尋找旋轉排序數組中的最小值(二分)

    題目鏈接:leetcode153

    題面

    在這里插入圖片描述

    題目大意

    題目中的旋轉可以理解成整個有序數組循環左移,找旋轉點相當于找這個左移的開頭,由于原序列有序,相當于找數組的最小值。數組中的元素不重復!

    解題思路

    暴力

    遍歷一次數組,尋找最小值。

    時間復雜度 O ( n ) O(n) O(n) ,空間復雜度 O ( 1 ) O(1) O(1)


    二分

    由于原序列有序,根據左移的特性,我們可以進行二分:

    • 如果 mid 的元素值小于等于右端點的元素值,顯然旋轉點就在 mid 的左邊,則此時 r = mid
    • 否則旋轉點在 mid 的右邊,則此時 l = mid + 1

    注意,由于二分寫法的不同,邊界情況要考慮好。


    代碼實現

    class Solution {
    public:
        int findMin(vector<int>& nums) {        
            int l = 0, r = nums.size()-1, mid;
            while (l < r) {
                mid = l + (r - l >> 1);
                if (nums[mid] <= nums[r]) r = mid;
                else l = mid + 1;
            }
            
            return nums[l];
        }
    };
    
    版權聲明:本文為calculate23原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/calculate23/article/details/108853298

    智能推薦

    數組刪除其中某個對象的方法

    數組刪除其中的對象或元素,在前端是比較常見的需求。 我現在比較常用的方法如下: 這種方法只適合刪除具有唯一標識的對象。 有沒有想要脫單的小伙伴,加入我們的脫單星球,認識更多優秀的小哥哥小姐姐 特此聲明,星球是免費的,但是創建星球的時候說是必須輸入金額,所以只能先私聊,我再加你免費加入!...

    圖床搭建以及圖床工具的使用

    為什么要用圖床和圖床工具? 比較下面三種md中的圖片url地址(均免費),你會使用哪一種? 選1?由于是本地路徑,文檔分享后給其他人打開后很可能顯示圖片加載失敗。 選2?雖然分享后可以顯示圖片,但能保證加載速度? 選3?我肯定選這種,即兼容2的瀏覽器訪問,又能保證訪問速度。 這樣就可以回答上面的問題了!保證瀏覽器訪問要用圖床,保證加載速度要用圖床工具,又不花錢想想就開心。 除此之外本篇博客還會講解...

    并發編程理論篇

    一、必備知識回顧 計算機又叫電腦,即通電的大腦,發明計算機是為了讓他通電之后能夠像人一樣去工作,并且它比人的工作效率更高,因為可以24小時不間斷 計算機五大組成部分 控制器 運算器 存儲器 輸入設備 輸出設備 計算機的核心真正干活的是CPU(控制器+運算器=中央處理器) 程序要想被計算機運行,它的代碼必須要先由硬盤讀到內存,之后cpu取指再執行 并發 看起來像同時運行的就可以稱之為并發 并行 真正...

    Java LinkedHashMap

    Java LinkedHashMap 前言 Map是我們在實際使用過程中常用的集合,HashMap在Java的實際開發中出鏡率很高,它通過hash算法實現了高效的非線程安全的集合,它有一個缺點就是,用戶插入集合的數據時無序,在我們需要一些有序的map的時候,我們就需要引入另外一個集合:LinkedHashMap。 LinkedHashMap是一個有序的非線程安全的集合,它是HashMap的子類,基...

    Spark Streaming處理文件(本地文件以及hdfs上面的文件)

    標題介紹文件流之前先介紹一下Dstream 下面是來自官網一段的說明,Discretized Streams或DStream是Spark Streaming提供的基本抽象。它表示連續的數據流,可以是從源接收的輸入數據流,也可以是通過轉換輸入流生成的已處理數據流。在內部,DStream由一系列連續的RDD表示,這是Spark對不可變的分布式數據集的抽象(有關更多詳細信息,請參見Spark編程指南)。...

    猜你喜歡

    《痞子衡嵌入式半月刊》 第 8 期

    痞子衡嵌入式半月刊: 第 8 期 這里分享嵌入式領域有用有趣的項目/工具以及一些熱點新聞,農歷年分二十四節氣,希望在每個交節之日準時發布一期。 本期刊是開源項目(GitHub: JayHeng/pzh-mcu-bi-weekly),歡迎提交 issue,投稿或推薦你知道的嵌入式那些事兒。 上期回顧 :《痞子衡嵌入式半月刊: 第 7 期》 嘮兩句 今天是小滿,小滿節氣意味著進入了大幅降水的雨季。痞子...

    (C++)二叉樹的線索化 / 線索二叉樹

    好久不見,朋友們!雖然我知道沒人看我的博客,但我還是想叨逼叨一下。啊,好久沒編程了(其實也就一周沒編),但你們知道,程序員一天不編程那能叫程序員么???雖然我不是程序員哈哈哈哈哈,但還是要有基本素養嘛。 繼續寫二叉樹,給自己立一個flag,就是這幾天要寫完之前沒做完的幾道題,和二叉樹紅黑樹各種樹之類的~~雖然有這個flag,但我還是很實誠地遵從自己的內心,買了一張明天的電影票,等我回來告訴你們好不...

    Linux內存管理:分頁機制

    《Linux內存管理:內存描述之內存節點node》 《Linux內存管理:內存描述之內存區域zone》 《Linux內存管理:內存描述之內存頁面page》 《Linux內存管理:內存描述之高端內存》 《Linux內存管理:分頁機制》 《內存管理:Linux Memory Management:MMU、段、分頁、PAE、Cache、TLB》 目錄 1 分頁機制 1.1 為什么使用多級頁表來完成映射 ...

    Logtail 混合模式:使用插件處理文件日志

    作為一個服務百萬機器的日志采集 agent,Logtail 目前已經提供了包括日志切分、日志解析(完整正則、JSON、分隔符)、日志過濾在內的常見處理功能,能夠應對絕大多數場景的處理需求。但有些時候,由于應用的歷史原因或是本身業務日志的復雜性,單一功能可能無法滿足所采集日志的處理需求,比如: 日志可能不再是單一格式,有可能同時由 JSON 或者分隔符日志組成。 日志格式可能也不固定,不同的業務邏輯...

    Q版緩沖區溢出教程-第一章讀書筆記

    Q版緩沖區溢出教程 1.3 神秘的windows系統 1.3.1 溢出舉例: 我們編譯運行之后的結果 現在我們把程序進行更改,數組的值進行一個變化,改為’abcdefgh’然后再編譯運行 程序運行沒有問題。 如果這個時候我們把程序再次加長的話,會發生什么,內容更改為’abcdefghijklmn’。 這個時候出了錯誤說內存越界。 1.3.3對溢出報錯...

    精品国产乱码久久久久久蜜桃不卡