75. sort colors

2020-06-23

2 minute read

You must solve this problem without using the library’s sort function.

利用计数排序这里的时间复杂度是 O(n), 空间复杂度是 O(m) m是颜色的基数, 这里m=3可以认为是常数.

 1class Solution {
 2    public void sortColors(int[] nums) {
 3        int [] cnt = new int[3];
 4        for (int n : nums) {
 5            cnt[n] ++;
 6        }
 7        int j = 0;
 8        for (int i = 0; i < 3; i++) {
 9            int c = cnt[i];
10            while (c-->0) {
11                nums[j++] = i;
12            }
13        }
14    }
15}

 1class Solution:
 2    def sortColors(self, nums: List[int]) -> None:
 3        """
 4        Do not return anything, modify nums in-place instead.
 5        """
 6        cnt =  [0]*3
 7        
 8        for i in nums:
 9            cnt[i] += 1
10        
11        j = 0
12        for i in range(3):
13            c = cnt[i]
14            while c > 0:
15                nums[j] = i
16                c -= 1
17                j += 1
18

one pass, two pointer double end swaps

这里的时间复杂度是 O(n)

 1class Solution {
 2    public void sortColors(int[] nums) {
 3        int l = 0;
 4        int r = nums.length - 1;
 5        
 6        int i = 0;
 7        while (i <= r) { //注意边界
 8            if (nums[i] == 2) {
 9                swap(nums, i, r);
10                r--; // 因为不知道换过来的是0还是1，所以指针不能前进
11            } else if (nums[i] == 0) {
12                swap(nums, i, l);
13                l++;
14                i++; // 因为换过来的一定大于等于0，所以指针可以前进
15            } else {
16                i++;
17            }
18        }
19    }
20    
21    private void swap(int[] nums, int i, int j) {
22        int tmp = nums[j];
23        nums[j] = nums[i];
24        nums[i] = tmp;
25    }
26}