【專題刷題】二分查找(二)

📝前言說明:

  • 本專欄主要記錄本人的基礎算法學習以及LeetCode刷題記錄,按專題劃分
  • 每題主要記錄:(1)本人解法 + 本人屎山代碼;(2)優質解法 + 優質代碼;(3)精益求精,更好的解法和獨特的思想(如果有的話)
  • 文章中的理解僅為個人理解。如有錯誤,感謝糾錯

🎬個人簡介:努力學習ing
📋本專欄:C++刷題專欄
📋其他專欄:C語言入門基礎,python入門基礎,C++學習筆記,Linux
🎀CSDN主頁 愚潤澤

視頻

  • 69. x 的平方根
    • 個人解
  • 35. 搜索插入位置
    • 個人解
  • 852. 山脈數組的峰頂索引
    • 個人解
  • 162. 尋找峰值
    • 個人解
  • 153. 尋找旋轉排序數組中的最小值
    • 個人解
    • 優質解
  • LCR 173. 點名
    • 個人解


69. x 的平方根

在這里插入圖片描述

個人解

思路:

  • 確定答案區間:[0, min(x, 46341)](46341 是 2^31 - 1 的平方根 + 1)
  • 問題轉換成:找平方 <= x 的右端點(因為題目向下取整)
  • mid選取判斷:因為向下取整,left = mid會死循環

用時:
屎山代碼:

class Solution {
public:int mySqrt(int x) {int left = 0, right = min(x, 46341);while(left < right) {unsigned int mid = left + (right - left + 1) / 2;if(mid * mid <= x)left = mid;elseright = mid - 1;}return left;}
};

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


35. 搜索插入位置

在這里插入圖片描述

個人解

思路:

  • 題目意思:有target就返回target,沒有就返回 >target 的第一個位置
  • 總結一下:就是返回 >= target 的第一個位置
  • 細節處理:模擬三種情況:1,正常找到target或者正常在數組中間插入;2,全部值都小于target;3,全部值都大于target(在這道題中要特殊處理全小于target的情況)

用時:5:00
屎山代碼:

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < target)left = mid + 1;elseright = mid;}// 特殊處理全小于target的情況if(nums[right] >= target)return right;elsereturn nums.size();}
};

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


852. 山脈數組的峰頂索引

在這里插入圖片描述

個人解

思路:

  • 二段性:每次和右邊的數比較
  • 右邊的數不存在 / 右邊的數 <= 當前數:山峰肯定在 [left, mid]
  • 右邊的數 > 當前數:山峰肯定在 [mid + 1, right]

用時:5:00
屎山代碼:

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 0, right = arr.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(mid + 1 == arr.size() || arr[mid + 1] <= arr[mid])right = mid;elseleft = mid + 1;}return right;}
};

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


162. 尋找峰值

在這里插入圖片描述
在這里插入圖片描述

個人解

思路:

  • 這道題的提示3:nums[i] != nums[i + 1],太重要了(保證了一定有一個峰值)
  • 每次和右側數字比較
  • > 右側的數字:峰值一定在[left ,mid](mid有可能是峰值)
  • < 右側的數字:峰值一定在[mid + 1, right]

用時:10:00(一開始沒看到提示3)
屎山代碼:

class Solution {
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[mid + 1])right = mid;elseleft = mid + 1;}return right;}
};

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


153. 尋找旋轉排序數組中的最小值

個人解

思路:

  • 利用數組的有序性二分,找最小
  • 但是問題在于:這里在翻轉以后可能出現兩段數組!一段數組上查找的時候,要判斷最小值會不會出行在另一段數組上
  • 如何判斷呢?如果真的有兩段數組,則第二段數組的最大值一定是nums[n-1],如果當前nums[mid] < nums[n - 1]代表在正確的數組上查找了,反之就是在錯誤的數組上查找了,要讓left移動到右邊

用時:15:00
屎山代碼:

class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size();int left = 0, right = n - 1;while(left < right){int mid = left + (right - left) / 2;if(mid + 1 == n || (nums[mid] < nums[mid + 1] && nums[mid] < nums[n - 1]))right = mid;elseleft = mid + 1;}return nums[right];}
};

時間復雜度:O(log n)
空間復雜度:O(1)


優質解

看了官方題解以后想到的:
在這里插入圖片描述

  • 如果翻轉了,產生了兩個數組,則最小值,一定在第二個數組上!!!
  • 并且,前一個數組的元素都大于第二個數組的元素
  • 那我們的比較基準就可以和最后一個值進行比較
  • > nums[n-1]:數組錯了,答案一定在[mid + 1, right]
  • < nums[n-1]:答案一定在[left, mid]mid也有可能是答案

代碼:

class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size();int left = 0, right = n - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < nums[n - 1])right = mid;elseleft = mid + 1;}return nums[right];}
};

LCR 173. 點名

個人解

思路:

  • 因為數組是升序排序的,且學號從0開始,利用學號和下標對應的特點,找出缺失值在哪一遍
  • mid == records[mid] ,則缺失值在 [mid + 1, right]
  • mid > records[left, mid]
  • 特殊判斷,最后一個同學缺席

用時:7:00
屎山代碼:

class Solution {
public:int takeAttendance(vector<int>& records) {int n = records.size();if(records[n - 1] == n - 1)return n;int left = 0, right = n - 1;while(left < right){int mid = left + (right - left) / 2;if(mid == records[mid])left = mid + 1;elseright = mid;}return records[right] - 1;}
};

時間復雜度:O(log n)
空間復雜度:O(1)


🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助,那簡直是太酷啦!
若有不足,還請大家多多指正,我們一起學習交流!
📢公主,王子:點贊👍→收藏?→關注🔍
感謝大家的觀看和支持!祝大家都能得償所愿,天天開心!!!

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/78422.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/78422.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/78422.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Java—ThreadLocal底層實現原理

首先&#xff0c;ThreadLocal 本身并不提供存儲數據的功能&#xff0c;當我們操作 ThreadLocal 的時候&#xff0c;實際上操作線程對象的一個名為 threadLocals 成員變量。這個成員變量的類型是 ThreadLocal 的一個內部類 ThreadLocalMap&#xff0c;它是真正用來存儲數據的容器…

Elasticsearch(ES)中的腳本(Script)

文章目錄 一. 腳本是什么&#xff1f;1. lang&#xff08;腳本語言&#xff09;2. source&#xff08;腳本代碼&#xff09;3. params&#xff08;參數&#xff09;4. id&#xff08;存儲腳本的標識符&#xff09;5. stored&#xff08;是否為存儲腳本&#xff09;6. script 的…

客戶聯絡中心能力與客戶匹配方式

在數字化時代&#xff0c;客戶聯絡中心作為企業與客戶溝通的核心樞紐&#xff0c;其服務能力與客戶需求的精準匹配至關重要。隨著客戶期望的不斷提升&#xff0c;傳統的“一刀切”服務模式已難以滿足個性化需求&#xff0c;如何通過智能化的手段實現服務能力與客戶的高效匹配&a…

深入理解網絡原理:UDP協議詳解

在計算機網絡中&#xff0c;數據的傳輸是通過各種協議實現的&#xff0c;其中用戶數據報協議&#xff08;UDP&#xff0c;User Datagram Protocol&#xff09;作為一種重要的傳輸層協議&#xff0c;廣泛應用于實時通信、視頻流、在線游戲等場景。本文將深入探討UDP協議的特性、…

vscode切換Python環境

跑深度學習項目通常需要切換python環境&#xff0c;下面介紹如何在vscode切換python環境&#xff1a; 1.點擊vscode界面左上角 2.在彈出框選擇對應kernel

【MCP Node.js SDK 全棧進階指南】中級篇(4):MCP錯誤處理與日志系統

前言 隨著MCP應用的規模和復雜性增長,錯誤處理與日志系統的重要性也日益凸顯。一個健壯的錯誤處理策略和高效的日志系統不僅可以幫助開發者快速定位和解決問題,還能提高應用的可靠性和可維護性。本文作為中級篇的第四篇,將深入探討MCP TypeScript-SDK中的錯誤處理與日志系統…

【Qt】文件

&#x1f308; 個人主頁&#xff1a;Zfox_ &#x1f525; 系列專欄&#xff1a;Qt 目錄 一&#xff1a;&#x1f525; Qt 文件概述 二&#xff1a;&#x1f525; 輸入輸出設備類 三&#xff1a;&#x1f525; 文件讀寫類 四&#xff1a;&#x1f525; 文件和目錄信息類 五&…

代碼隨想錄算法訓練營第五十八天 | 1.拓撲排序精講 2.dijkstra(樸素版)精講 卡碼網117.網站構建 卡碼網47.參加科學大會

1.拓撲排序精講 題目鏈接&#xff1a;117. 軟件構建 文章講解&#xff1a;代碼隨想錄 思路&#xff1a; 把有向無環圖進行線性排序的算法都可以叫做拓撲排序。 實現拓撲排序的算法有兩種&#xff1a;卡恩算法&#xff08;BFS&#xff09;和DFS&#xff0c;以下BFS的實現思…

Qt實現語言切換的完整方案

在Qt中實現語言動態切換需要以下幾個關鍵步驟&#xff0c;我將提供一個完整的實現方案&#xff1a; 一、準備工作 在代碼中使用tr()標記所有需要翻譯的字符串 cpp button->setText(tr("Submit")); 創建翻譯文件 在.pro文件中添加&#xff1a; qmake TRANSLATION…

面試中被問到mybatis與jdbc有什么區別怎么辦

1. 核心區別 維度JDBCMyBatis抽象層級底層API&#xff0c;直接操作數據庫高層持久層框架&#xff0c;封裝JDBC細節代碼量需要手動編寫大量樣板代碼&#xff08;連接、異常處理等&#xff09;通過配置和映射減少冗余代碼SQL管理SQL嵌入Java代碼&#xff0c;維護困難SQL與Java代…

用于協同顯著目標檢測的小組協作學習 2021 GCoNet(總結)

摘要 一 介紹 問題一&#xff1a;以往的研究嘗試利用相關圖像之間的一致性&#xff0c;通過探索不同的共享線索[12, 13, 14]或語義連接[15, 16, 17]&#xff0c;來助力圖像組內的共同顯著目標檢測&#xff08;CoSOD&#xff09;&#xff0c;什么意思&#xff1f; 一方面是探…

OpenCV 圖形API(62)特征檢測-----在圖像中查找最顯著的角點函數goodFeaturesToTrack()

操作系統&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 編程語言&#xff1a;C11 算法描述 確定圖像上的強角點。 該函數在圖像或指定的圖像區域內找到最顯著的角點&#xff0c;如文獻[240]中所述。 函數使用 cornerMinEigenVal 或 cor…

MySQL引擎分類與選擇、SQL更新底層實現、分庫分表、讀寫分離、主從復制 - 面試實戰

MySQL引擎分類與選擇、SQL更新底層實現、分庫分表、讀寫分離、主從復制 - 面試實戰 故事背景&#xff1a; 今天&#xff0c;我們模擬一場互聯網大廠Java求職者的面試場景。面試官將針對MySQL的核心技術點進行提問&#xff0c;涵蓋MySQL引擎分類與選擇、SQL更新底層實現、分庫…

如何確保微型導軌的質量穩定?

微型導軌在精密機械中扮演著至關重要的角色&#xff0c;它們不僅影響設備的性能&#xff0c;還決定了產品的壽命。那么&#xff0c;如何通過一些關鍵步驟來提高微型導軌的穩定性呢&#xff1f; 1、嚴格篩選供應商&#xff1a;選擇具備高品質保證能力的供應商&#xff0c;確保原…

Golang編程拒絕類型不安全

簡介 在 Go 中&#xff0c;標準庫提供了多種容器類型&#xff0c;如 list、ring、heap、sync.Pool 和 sync.Map。然而&#xff0c;這些容器默認是類型不安全的&#xff0c;即它們可以接受任何類型的值&#xff0c;這可能導致運行時錯誤。為了提升代碼的類型安全性和可維護性&am…

什么是 JSON?學習JSON有什么用?在springboot項目里如何實現JSON的序列化和反序列化?

作為一個學習Javaweb的新手&#xff0c;理解JSON的序列化和反序列化非常重要&#xff0c;因為它在現代Web開發&#xff0c;特別是Spring Boot中無處不在。 什么是 JSON&#xff1f; 首先&#xff0c;我們簡單了解一下JSON (JavaScript Object Notation)。 JSON 是一種輕量級的…

iOS/Android 使用 C++ 跨平臺模塊時的內存與生命周期管理

在移動應用開發領域,跨平臺開發已經成為一種不可忽視的趨勢。隨著智能手機市場的持續擴張,開發者需要同時滿足iOS和Android兩大主流平臺的需求,而這往往意味著重復的工作量和高昂的維護成本。跨平臺開發的目標在于通過一套代碼庫實現多平臺的支持,從而降低開發成本、加速產…

【AAudio】A2dp sink創建音頻軌道的源碼流程分析

一、AAudio概述 AAudio 是 Android 8.0(API 級別 26)引入的 C/C++ 原生音頻 API,專為需要低延遲、高性能音頻處理的應用設計,尤其適用于實時音頻應用(如音頻合成器、音樂制作工具、游戲音效等)。 1.1 主要特點 低延遲:通過減少音頻數據在內核與用戶空間之間的拷貝,直…

Spring中配置 Bean 的兩種方式:XML 配置 和 Java 配置類

在 Spring 框架中,配置 Bean 的方式主要有兩種:XML 配置 和 Java 配置類。這兩種方式都可以實現將對象注冊到 Spring 容器中,并通過依賴注入進行管理。本文將詳細介紹這兩種配置方式的步驟,并提供相應的代碼示例。 1. 使用 XML 配置的方式 步驟 創建 Spring 配置文件 創建…

海之淀攻略

家長要做的功課 家長可根據孩子情況&#xff0c;需要做好以下功課&#xff1a; 未讀小學的家長&#xff1a;了解小學小升初派位初中校額到校在讀小學的家長&#xff1a;了解小升初派位初中校額到校在讀初中的家長&#xff1a;了解初中校額到校 越是高年級的家長&#xff0c;…