75.sort-colors.md

题目地址

https://leetcode.com/problems/sort-colors/description/

题目描述

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.

Note: You are not suppose to use the library's sort function for this problem.

Example:

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

A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's. Could you come up with a one-pass algorithm using only constant space?

思路

其实就是排序，而且没有要求稳定性，就是用啥排序算法都行。 题目并没有给出数据规模，因此我默认数据量不大，直接选择了冒泡排序

关键点解析

冒泡排序的时间复杂度是N平方，无法优化，但是可以进一步优化常数项， 比如循环的起止条件。 由于每一次遍历都会将最后一位“就位”，因此内层循环的截止条件就可以是 nums.length - i， 而不是 nums.length, 可以省一半的时间。

代码

/*
 * @lc app=leetcode id=75 lang=javascript
 *
 * [75] Sort Colors
 *
 * https://leetcode.com/problems/sort-colors/description/
 *
 * algorithms
 * Medium (41.41%)
 * Total Accepted:    297K
 * Total Submissions: 716.1K
 * Testcase Example:  '[2,0,2,1,1,0]'
 *
 * 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.
 * 
 * Note: You are not suppose to use the library's sort function for this
 * problem.
 * 
 * Example:
 * 
 * 
 * Input: [2,0,2,1,1,0]
 * Output: [0,0,1,1,2,2]
 * 
 * Follow up:
 * 
 * 
 * A rather straight forward solution is a two-pass algorithm using counting
 * sort.
 * First, iterate the array counting number of 0's, 1's, and 2's, then
 * overwrite array with total number of 0's, then 1's and followed by 2's.
 * Could you come up with a one-pass algorithm using only constant space?
 * 
 * 
 */
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    function swap(nums, i, j) {
       const temp = nums[i];
       nums[i] = nums[j];
       nums[j] = temp; 
    }
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = 0; j < nums.length - i; j++) {
            if (nums[j] < nums[j -1]) {
                swap(nums, j - 1 , j)
            }
            
        }      
    }
};