成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Sort Colors 顏色排序

muddyway / 3246人閱讀

摘要：當遇到時，將其和序列前面一個數(shù)交換，然后將序列的指針向前移。這樣，當我們遍歷到序列開頭時，實際上我們已經(jīng)排好序了，因為所有都被交換到了前面，所有都被交換到了后面。

Sort Colors 
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.


Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
交換法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

我們先用兩個指針，一個指向已經(jīng)排好序的0的序列的后一個點，一個指向已經(jīng)排好序的2的序列的前一個點。這樣在一開始，兩個指針是指向頭和尾的，因為我們還沒有開始排序。然后我們遍歷數(shù)組，當遇到0時，將其和0序列后面一個數(shù)交換，然后將0序列的指針向后移。當遇到2時，將其和2序列前面一個數(shù)交換，然后將2序列的指針向前移。遇到1時，不做處理。這樣，當我們遍歷到2序列開頭時，實際上我們已經(jīng)排好序了，因為所有0都被交換到了前面，所有2都被交換到了后面。

代碼 
public class Solution {
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        int i = 0;
        while(i <= right){
            // 遇到0交換到前面
            if(nums[i] == 0){
                swap(nums, i, left);
                left++;
                // 因為左邊必定有序，所以可以直接i++
                i++;
            // 遇到2交換到后面
            } else if(nums[i] == 2){
                swap(nums, i, right);
                right--;
            } else {
            // 遇到1跳過 
                i++;
            }
        }
    }
    
    private void swap(int[] nums, int i1, int i2){
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64537.html

相關(guān)文章

  • leetcode75. Sort Colors

    摘要：將數(shù)組中的數(shù)字排序，盡量實現(xiàn)時間復(fù)雜度。然后在第二次遍歷數(shù)組的過程中，將相應(yīng)次數(shù)的，，依序填入數(shù)組中。我們要確保左指針之前的數(shù)值全部是，右指針之后的數(shù)值全部是。這樣他就可以確保左右指針之間的數(shù)字為，從而實現(xiàn)，，的排序。 題目要求 Given an array with n objects colored red, white or blue, sort them so that obj...

    weizx 評論0 收藏0

  • 75. Sort Colors

    摘要：題目鏈接這題是給數(shù)組排序，數(shù)組里面只有個變量。一個方法是用類似，個桶，統(tǒng)計三個變量出現(xiàn)的個數(shù)，然后重構(gòu)數(shù)組即可。還有一種方法是用，參考算法這本書上的講解和程序 75. Sort Colors 題目鏈接：https://leetcode.com/problems... 這題是給數(shù)組排序，數(shù)組里面只有3個變量。一個方法是用類似bucket sort，3個桶，統(tǒng)計三個變量出現(xiàn)的個數(shù)，然后重構(gòu)...

    _ivan 評論0 收藏0

  • 詳解數(shù)組(Array)引用類型

    摘要：例如，會刪除數(shù)組中的前兩項。插入的項數(shù)不必與刪除的項數(shù)相等。這兩個方法都接收兩個參數(shù)要查找的項和可選的表示查找起點位置的索引。對數(shù)組中的每一項運行給定函數(shù)，返回每次函數(shù)調(diào)用的結(jié)果組成的數(shù)組。 除Object類型外,Array是最常用的類型,Array對象與其他語言相比有著自己的不同之處,首先同一數(shù)組對象的不同項可以保存不同類型的數(shù)據(jù),其次數(shù)組對象的長短可以動態(tài)改變. showImg(...

    afishhhhh 評論0 收藏0

  • Vue+Vue-router+Vuex項目實戰(zhàn)

    摘要：實現(xiàn)電商網(wǎng)站效果展示下載代碼安裝依賴啟動項目運行環(huán)境需求分析登錄頁面商品列表頁網(wǎng)站首頁購物車頁實現(xiàn)結(jié)算商品詳情頁可按顏色品牌對商品進行篩選，單擊選中，再次點擊取消根據(jù)價格進行升序降序銷量降序排列商品列表顯示圖片名稱銷量顏色單價實時顯示 shopping vue + vue-router + vuex實現(xiàn)電商網(wǎng)站 效果展示 showImg(https://user-gold-cdn.xi...

    zlyBear 評論0 收藏0

  • Vue+Vue-router+Vuex項目實戰(zhàn)

    摘要：實現(xiàn)電商網(wǎng)站效果展示下載代碼安裝依賴啟動項目運行環(huán)境需求分析登錄頁面商品列表頁網(wǎng)站首頁購物車頁實現(xiàn)結(jié)算商品詳情頁可按顏色品牌對商品進行篩選，單擊選中，再次點擊取消根據(jù)價格進行升序降序銷量降序排列商品列表顯示圖片名稱銷量顏色單價實時顯示 shopping vue + vue-router + vuex實現(xiàn)電商網(wǎng)站 效果展示 showImg(https://user-gold-cdn.xi...

    Chiclaim 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<