• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • 【劍指offer之二分查找】二分查找類型

    標簽: 劍指offer  算法  leetcode  數據結構  二分查找  


    概述

    本篇文章記錄劍指offer標簽為二分查找類的題。二分的模板太多了,本篇文章用的二分模板都是我之前發過的模板,附上鏈接:【算法模板】二分查找下面的題都是在力扣上面做的,可以按照題名搜索即可

    題不太多,建議刷刷leetcode上面二分的題,leetcode上面刷個10多道就夠了

    劍指 Offer 53 - II 0~n-1中缺失的數字

    image-20201114230704922

    二分

    由題意,我們可以將該數組分成兩部分

    image-20201105123409994

    第一部分是0 - x-1中, i = nums[i] , 第二部分是x - n - 1種中, i != nums[i]的則可以使用二分查找,我們要找到位置就是第一個i != nums[i]的位置。

    邊界情況是整個數組都是上圖中藍顏色的部分,我們要返回的值就是下一個數了

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

    代碼:

    class Solution {
    public:
        int getMissingNumber(vector<int>& nums) {
            if (nums.empty()) return 0;
            int l = 0 , r = nums.size() - 1;
            //二分查找,找到第一個 i != nums[i]的位置
            while ( l < r){
                int mid = l + r >> 1;
                if (mid != nums[mid]) r = mid;
                else l = mid + 1;
            }
            //邊界情況,整個數組都是升序
            if (nums[l] == l) l ++;
            return l;
        }
    };
    

    劍指 Offer 53 - I 在排序數組中查找數字 I

    image-20201114232142733

    二分

    因為是排序好的數組,所以相同元素一定是連續存儲在數組中的。要統計出現次數,我們只需要找到該數字在數組中第一次出現的位置和最后一次出現的位置即可

    image-20201114233207506

    我們需要做兩次二分查找,找第一次個>=x的位置和第一個<=x的位置。這和二分模板是一模一樣,具體想看模板請翻閱到文章的頭部。

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

    代碼:

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            //特判空數組
            if (nums.empty()) return 0;
            //第一次二分查找
            int start;
            int l = 0 , r = nums.size() - 1;
            while (l < r){
                int mid = l + r >> 1;
                if (nums[mid] >= target) r = mid ;
                else l = mid + 1;
            }
            //數組不存在target
            if (nums[l] != target) return 0;
            start = l;
            //第二次二分查找
            l = 0 , r = nums.size() - 1;
            while (l < r){
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= target) l = mid;
                else r = mid - 1;
            }
            return l - start + 1;
        }
    };
    

    劍指 Offer 11 旋轉數組的最小數字

    image-20201114233323101

    二分

    image-20201114233727418

    如圖,本來是遞增的序列經過旋轉后會變成這樣,前面一段是遞增的,后面一段也是遞增的。者兩段是被第一個元素分割的

    我們可以用二分找到第一段的最后一個位置,然后判斷第二段是否存在

    • 如果第二段存在,則第二段的第一個位置即最小元素
    • 如果第二段不存在,則第一段的第一個元素為最小元素

    該題由于有重復元素,我們所以可能存在第一段的開頭和第二段的結尾可能都是相等的,我們需要用第一個元素作為兩段的分割,因為存在相等元素,不能保證我們能夠分清兩端,所以需要將第二段末尾和第一段的第一個元素相同的刪去。這樣能夠保證我們能夠分割兩段。

    時間復雜度O(logN),O(1)

    代碼:

    class Solution {
    public:
        int minArray(vector<int>& nums) {
            //去除第二段和第一段第一個元素相同的元素
            int k = nums.size() - 1;
            while (k >= 0 && nums[k] == nums[0]) k --;
            //數組全是相同的
            if (k < 0) return nums[0];
            //二分,找到第一段最后一個元素
            int l = 0 , r = k ;
            while (l < r){
                int mid = l + r + 1 >> 1;
                if (nums[mid] >= nums[0]) l = mid;
                else r = mid - 1;
            }
            //判斷第二段是否存在
            if (r == k) return nums[0];
            return nums[r + 1];
        }
    };
    

    r = mid - 1;
    }
    //判斷第二段是否存在
    if (r == k) return nums[0];
    return nums[r + 1];
    }
    };

    
    
    版權聲明:本文為Miiiiiiiiiii原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/Miiiiiiiiiii/article/details/109698732

    智能推薦

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

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

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

    為什么要用圖床和圖床工具? 比較下面三種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對溢出報錯...

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