成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[Leetcode] Sort Colors 顏色排序

muddyway / 3284人閱讀

摘要：當(dāng)遇到時(shí)，將其和序列前面一個(gè)數(shù)交換，然后將序列的指針向前移。這樣，當(dāng)我們遍歷到序列開頭時(shí)，實(shí)際上我們已經(jīng)排好序了，因?yàn)樗卸急唤粨Q到了前面，所有都被交換到了后面。

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ù)雜度

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

思路

我們先用兩個(gè)指針，一個(gè)指向已經(jīng)排好序的0的序列的后一個(gè)點(diǎn)，一個(gè)指向已經(jīng)排好序的2的序列的前一個(gè)點(diǎn)。這樣在一開始，兩個(gè)指針是指向頭和尾的，因?yàn)槲覀冞€沒有開始排序。然后我們遍歷數(shù)組，當(dāng)遇到0時(shí)，將其和0序列后面一個(gè)數(shù)交換，然后將0序列的指針向后移。當(dāng)遇到2時(shí)，將其和2序列前面一個(gè)數(shù)交換，然后將2序列的指針向前移。遇到1時(shí)，不做處理。這樣，當(dāng)我們遍歷到2序列開頭時(shí)，實(shí)際上我們已經(jīng)排好序了，因?yàn)樗?都被交換到了前面，所有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++;
                // 因?yàn)樽筮叡囟ㄓ行?，所以可以直接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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64537.html

相關(guān)文章

  • leetcode75. Sort Colors

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

    weizx 評(píng)論0 收藏0

  • 75. Sort Colors

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

    _ivan 評(píng)論0 收藏0

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

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

    afishhhhh 評(píng)論0 收藏0

  • Vue+Vue-router+Vuex項(xiàng)目實(shí)戰(zhàn)

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

    zlyBear 評(píng)論0 收藏0

  • Vue+Vue-router+Vuex項(xiàng)目實(shí)戰(zhàn)

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

    Chiclaim 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<