leetcode - [75] Sort Colors

2020/04/27

题目描述

Given an array with n objects colored red, white or blue, sort them in-place 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.

给你一个数组,其中只包含012三个数组,将其升序排列。

举个例子:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

解法1

我的第一反应使用插入排序

public void sortColors(int[] nums) {
    if (nums == null || nums.length == 0) return;
    for (int i = 1; i < nums.length; i++){
        int cur = i;
        while (cur > 0){
            if (nums[cur] < nums[cur - 1]){
                swap(nums, cur, cur - 1);
            }
            cur--;
        }
    }
}

public void swap(int[] arr, int x, int y){
    int tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
}

但是效率太低,时间复杂度为O(N^2)

解法2

Thanks @meganlee

可以先遍历一次数组,统计所有012出现的次数,然后依次重新赋值:

用空间换时间。

public void sortColors(int[] nums) {
    if (nums == null || nums.length == 0) return;
    int cur = 0;
    int[] arr = new int[3];
    for (int n: nums){
        arr[n]++;
    }
    while (arr[0] > 0){
        nums[cur++] = 0;
        arr[0]--;
    }
    while (arr[1] > 0){
        nums[cur++] = 1;
        arr[1]--;
    }
    while (arr[2] > 0){
        nums[cur++] = 2;
        arr[2]--;
    }
}

再简化一下:

public void sortColors(int[] nums) {
    if (nums == null || nums.length == 0) return;
    int[] arr = new int[3];
    for (int n: nums){
        arr[n]++;
    }
    for (int i = 0; i < nums.length; i++){
        if (i < arr[0]){
            nums[i] = 0;
        } else if (i < (arr[0] + arr[1])){
            nums[i] = 1;
        } else {
            nums[i] = 2;
        }
    }
}

解法3 - Update 2020_0517

Update at 2020_0714

重新梳理下该解法的思路:

首先,我们需要三个指针,分别是左、右指针和存储0的边界指针。

由于数组中只有三个值,分别对应三种情况:

第一种,值为0,那么需要做什么事情?

  • 0
  • 左指针右移一位。
  • zeroOrder指针也向右移一位。

第二种,值为1: 左指针右移一位即可。

第三种,值为2

  • 互换左右两侧值。
  • 右指针左移一位。

再来看一种最惊艳的解法:

public void sortColors(int[] nums) {
    if (nums == null || nums.length == 0) return;
    
    int lo = 0, hi = nums.length - 1, zeroBorder = 0;
    
    while (lo <= hi){
        if (nums[lo] == 0){
            swap(nums, lo++, zeroBorder++);
        } else if (nums[lo] == 2){
            swap(nums, lo, hi--);
        } else {
            lo++;
        }
    }
}

这里再强调一下,为什么while循环的条件是lo <= hi

来看下[2, 0, 1]这个例子:

冒泡、选择、归并排序合计

冒泡排序

private static void sortColorsUsingBubble(int[] nums) {
    for (int i = nums.length - 1; i > 0; i--){
        int j = 1;
        while (j <= i){
            if (nums[j] < nums[j - 1]){
                Utils.swap(nums, j, j - 1);
            }
            j++;
        }
    }
}

选择排序

private static void sortColorsUsingSelection(int[] nums) {
    int len = nums.length;
    for (int i = len - 1; i > 0; i--){
        int j = 1, maxIndex = 0;
        while (j <= i){
            if (nums[j] > nums[maxIndex]){
                maxIndex = j;
            }
            j++;
        }
        if (i != maxIndex){
            Utils.swap(nums, i, maxIndex);
        }
    }
}

归并排序

private static void sortColorUsingMerge(int[] nums) {
    seperate(nums, 0, nums.length - 1);
}

private static void seperate(int[] nums, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + ((hi - lo) >> 1);
    seperate(nums, lo, mid);
    seperate(nums, mid + 1, hi);
    doMerge(nums, lo, mid + 1, hi);
}

private static void doMerge(int[] nums, int lo, int mid, int hi) {
    int[] left  = new int[mid - lo];
    int[] right = new int[hi - mid + 1];

    for (int i = lo; i < mid; i++){
        left[i - lo] = nums[i];
    }

    for (int j = mid; j <= hi; j++){
        right[j - mid] = nums[j];
    }

    int i = 0, j = 0, k = lo;
    while (i < left.length && j < right.length){
        if (left[i] < right[j]){
            nums[k++] = left[i++];
        } else {
            nums[k++] = right[j++];
        }
    }

    while (i < left.length){
        nums[k++] = left[i++];
    }

    while (j < right.length){
        nums[k++] = right[j++];
    }
}

Enjoy it!


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory