<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0033. 搜索旋轉排序數組 ## 題目地址(33. 搜索旋轉排序數組) <https://leetcode-cn.com/problems/search-in-rotated-sorted-array/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個升序排列的整數數組 nums ,和一個整數 target 。 假設按照升序排序的數組在預先未知的某個點上進行了旋轉。(例如,數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。 請你在數組中搜索 target ,如果數組中存在這個目標值,則返回它的索引,否則返回 -1 。 示例 1: 輸入:nums = [4,5,6,7,0,1,2], target = 0 輸出:4 示例 2: 輸入:nums = [4,5,6,7,0,1,2], target = 3 輸出:-1 示例 3: 輸入:nums = [1], target = 0 輸出:-1 提示: 1 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4 nums 中的每個值都 獨一無二 nums 肯定會在某個點上旋轉 -10^4 <= target <= 10^4 ``` ``` ## 前置知識 - 數組 - 二分法 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這是一個我在網上看到的前端頭條技術終面的一個算法題。 題目要求時間復雜度為logn,因此基本就是二分法了。 這道題目不是直接的有序數組,不然就是easy了。 首先要知道,我們隨便選擇一個點,將數組分為前后兩部分,其中一部分一定是有序的。 具體步驟: - 我們可以先找出mid,然后根據mid來判斷,mid是在有序的部分還是無序的部分 假如mid小于start,則mid一定在右邊有序部分。 假如mid大于等于start, 則mid一定在左邊有序部分。 > 注意等號的考慮 - 然后我們繼續判斷target在哪一部分, 我們就可以舍棄另一部分了 我們只需要比較target和有序部分的邊界關系就行了。 比如mid在右側有序部分,即\[mid, end\] 那么我們只需要判斷 target >= mid && target <= end 就能知道target在右側有序部分,我們就 可以舍棄左邊部分了(start = mid + 1), 反之亦然。 我們以(\[6,7,8,1,2,3,4,5\], 4)為例講解一下: ![](https://img.kancloud.cn/c5/7c/c57cda5ed34a92aadf4eef52275b90ab_663x396.jpg) ![](https://img.kancloud.cn/cf/78/cf781862b88ac93763d6ce7bcfabaffd_609x650.jpg) ## 關鍵點解析 - [二分法](binary-search.html) - 找出有序區間,然后根據target是否在有序區間舍棄一半元素 ## 代碼 - 語言支持: Javascript,Python3 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=33 lang=javascript * * [33] Search in Rotated Sorted Array */</span> <span class="hljs-title">/** * @param {number[]} nums * @param {number} target * @return {number} */</span> <span class="hljs-keyword">var</span> search = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums, target</span>) </span>{ <span class="hljs-title">// 時間復雜度:O(logn)</span> <span class="hljs-title">// 空間復雜度:O(1)</span> <span class="hljs-title">// [6,7,8,1,2,3,4,5]</span> <span class="hljs-keyword">let</span> start = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> end = nums.length - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span> (start <= end) { <span class="hljs-keyword">const</span> mid = start + ((end - start) >> <span class="hljs-params">1</span>); <span class="hljs-keyword">if</span> (nums[mid] === target) <span class="hljs-keyword">return</span> mid; <span class="hljs-title">// [start, mid]有序</span> <span class="hljs-title">// ???注意這里的等號</span> <span class="hljs-keyword">if</span> (nums[mid] >= nums[start]) { <span class="hljs-title">//target 在 [start, mid] 之間</span> <span class="hljs-title">// 其實target不可能等于nums[mid], 但是為了對稱,我還是加上了等號</span> <span class="hljs-keyword">if</span> (target >= nums[start] && target <= nums[mid]) { end = mid - <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> { <span class="hljs-title">//target 不在 [start, mid] 之間</span> start = mid + <span class="hljs-params">1</span>; } } <span class="hljs-keyword">else</span> { <span class="hljs-title">// [mid, end]有序</span> <span class="hljs-title">// target 在 [mid, end] 之間</span> <span class="hljs-keyword">if</span> (target >= nums[mid] && target <= nums[end]) { start = mid + <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> { <span class="hljs-title">// target 不在 [mid, end] 之間</span> end = mid - <span class="hljs-params">1</span>; } } } <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span>; }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">search</span><span class="hljs-params">(self, nums: List[int], target: int)</span> -> int:</span> <span class="hljs-string">"""用二分法,先判斷左右兩邊哪一邊是有序的,再判斷是否在有序的列表之內"""</span> <span class="hljs-keyword">if</span> len(nums) <= <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span> left = <span class="hljs-params">0</span> right = len(nums) - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> left < right: mid = (right - left) // <span class="hljs-params">2</span> + left <span class="hljs-keyword">if</span> nums[mid] == target: <span class="hljs-keyword">return</span> mid <span class="hljs-title"># 如果中間的值大于最左邊的值,說明左邊有序</span> <span class="hljs-keyword">if</span> nums[mid] > nums[left]: <span class="hljs-keyword">if</span> nums[left] <= target <= nums[mid]: right = mid <span class="hljs-keyword">else</span>: <span class="hljs-title"># 這里 +1,因為上面是 <= 符號</span> left = mid + <span class="hljs-params">1</span> <span class="hljs-title"># 否則右邊有序</span> <span class="hljs-keyword">else</span>: <span class="hljs-title"># 注意:這里必須是 mid+1,因為根據我們的比較方式,mid屬于左邊的序列</span> <span class="hljs-keyword">if</span> nums[mid+<span class="hljs-params">1</span>] <= target <= nums[right]: left = mid + <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: right = mid <span class="hljs-keyword">return</span> left <span class="hljs-keyword">if</span> nums[left] == target <span class="hljs-keyword">else</span> <span class="hljs-params">-1</span> ``` ``` **復雜度分析** - 時間復雜度:O(logN)O(logN)O(logN) - 空間復雜度:O(1)O(1)O(1) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看