Warna Isih Leetcode

Intuisi

Gerakan asas datang daripada pengisihan.

Pendekatan

Dalam pendekatan naif, kita boleh mengisih tatasusunan menggunakan fungsi pengisihan terbina. Kerumitan masa ialah O(N*log(N)).

• Optimumkan: Memandangkan kita hanya mengisih tiga nombor, kita boleh menggunakan konsep pengisihan mengira. Jejaki bilangan sifar dan bilangan satu dalam tatasusunan. # Kerumitan

• Kerumitan masa: O(N)

• Kerumitan ruang: O(1)

Kod

class Solution {
    public void sortColors(int[] nums) {
        int countZero = 0;
        int countOne  =  0;
        for(int num: nums){
            switch(num){
                case 0:
                    countZero++;
                    break;
                case 1:
                    countOne++;
            }
        }
        int currentIndex = -1;
        while(0<countZero--){
            nums[++currentIndex] = 0;
            // countZero--;
        }
        while(0<countOne--){
            nums[++currentIndex] = 1;
            // countOne--;
        }
        while(currentIndex<nums.length-1){
            nums[++currentIndex] = 2;
        }
    }
}

Repo GitHub untuk lebih banyak penyelesaian: Git
Profil Leetcode: Leetcode: devn007

Atas ialah kandungan terperinci Warna Isih Leetcode. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!