<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>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 0075. 顏色分類 ## 題目地址(75. 顏色分類) <https://leetcode-cn.com/problems/sort-colors/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個包含紅色、白色和藍色,一共 n 個元素的數組,原地對它們進行排序,使得相同顏色的元素相鄰,并按照紅色、白色、藍色順序排列。 此題中,我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色。 注意: 不能使用代碼庫中的排序函數來解決這道題。 示例: 輸入: [2,0,2,1,1,0] 輸出: [0,0,1,1,2,2] 進階: 一個直觀的解決方案是使用計數排序的兩趟掃描算法。 首先,迭代計算出0、1 和 2 元素的個數,然后按照0、1、2的排序,重寫當前數組。 你能想出一個僅使用常數空間的一趟掃描算法嗎? ``` ``` ## 前置知識 - [荷蘭國旗問題](https://en.wikipedia.org/wiki/Dutch_national_flag_problem) - 排序 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這個問題是典型的荷蘭國旗問題 ([https://en.wikipedia.org/wiki/Dutch\_national\_flag\_problem)。](https://en.wikipedia.org/wiki/Dutch_national_flag_problem%EF%BC%89%E3%80%82) 因為我們可以將紅白藍三色小球想象成條狀物,有序排列后正好組成荷蘭國旗。 有兩種解決思路。 ## 解法一 - 遍歷數組,統計紅白藍三色球(0,1,2)的個數 - 根據紅白藍三色球(0,1,2)的個數重排數組 這種思路的時間復雜度:O(n)O(n)O(n),需要遍歷數組兩次。 ## 解法二 我們可以把數組分成三部分,前部(全部是 0),中部(全部是 1)和后部(全部是 2)三個部分。每一個元素(紅白藍分別對應 0、1、2)必屬于其中之一。將前部和后部各排在數組的前邊和后邊,中部自然就排好了。 我們用三個指針,設置兩個指針 begin 指向前部的末尾的下一個元素(剛開始默認前部無 0,所以指向第一個位置),end 指向后部開頭的前一個位置(剛開始默認后部無 2,所以指向最后一個位置),然后設置一個遍歷指針 current,從頭開始進行遍歷。 這種思路的時間復雜度也是O(n)O(n)O(n), 只需要遍歷數組一次。 ### 關鍵點解析 - 荷蘭國旗問題 - counting sort ### 代碼 代碼支持: Python3 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">sortColors</span><span class="hljs-params">(self, nums: List[int])</span> -> <span class="hljs-keyword">None</span>:</span> <span class="hljs-string">""" Do not return anything, modify nums in-place instead. """</span> p0 = cur = <span class="hljs-params">0</span> p2 = len(nums) - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> cur <= p2: <span class="hljs-keyword">if</span> nums[cur] == <span class="hljs-params">0</span>: nums[cur], nums[p0] = nums[p0], nums[cur] p0 += <span class="hljs-params">1</span> cur += <span class="hljs-params">1</span> <span class="hljs-keyword">elif</span> nums[cur] == <span class="hljs-params">2</span>: nums[cur], nums[p2] = nums[p2], nums[cur] p2 -= <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: cur += <span class="hljs-params">1</span> ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度: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>

                              哎呀哎呀视频在线观看