Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The Dutch national flag is red, white and blue. The French national flag and the Russian national flag are red, white and blue

75. Color classification [medium]

Leetcode-cn.com/problems/so…

Given an array of n red, white, and blue elements, sort them in place so that the elements of the same color are adjacent and sorted in red, white, and blue order.

In this case, we used integers 0, 1, and 2 to represent red, white, and blue, respectively.

Go through twice

A very simple solution to traverse both sides, looking for the 0 in front and the 2 in back.

/ * * *@param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let first = 0;
    let last = nums.length - 1;
    // For the first positive traversal, move all zeros to the far left
    for(let i = 0; i < nums.length; i++){
        if(nums[i] === 0){ swap(nums, i, first); first++; }}// Move all the 2's to the right for the second time in reverse order
    for(let i = nums.length - 1; i >= 0; i--){
        if(nums[i] === 2){ swap(nums, i, last); last--; }}};function swap(nums,i,j){
    let temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
Copy the code

You can also find them in order, 0 in front, 1 in the middle, the same.

var sortColors = function(nums) {
    let first = 0
    for(let i = 0; i < nums.length; i++){
        if(nums[i] === 0){ swap(nums, i, first); first++; }}for(let i = first; i < nums.length; i++){
        if(nums[i] === 1){ swap(nums, i, first); first++; }}};Copy the code

[Solution 2] Two layer cyclic bubble sort

Many in place sorting algorithms can [bubble] [select] [insert], etc

More information about sorting algorithms can be found in this blog post: Summary of classic sorting algorithms -JavaScript description – illustration – complexity analysis

var sortColors = function(nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length - i -1; j++) {
      if (nums[j] > nums[j + 1]) {
        swap(nums, j, j + 1); }}}};Copy the code

【 solution 3 】 Traverse once + loop invariant

I and j swap 0 for nums[I], 2 for nums[j], and skip 1 for nothing

Define loop invariants

[0, i) === 0
(i, k) === 1
(j, nums.length-1= = =2
Copy the code

The termination condition is k===j

var sortColors = function(nums) {
    let i = 0;
    let j = nums.length - 1;
    // Iterate over the nums to the last pointer position
    for(let k = 0; k <= j; k++){
        if(nums[k] === 0) {// The 0 and the header pointer are swapped
            swap(nums, k, i);
            // The header pointer moves back
            i++;
        }else if(nums[k] === 2) {// The 2 and the tail pointer are swapped
            swap(nums, k, j);
            // The tail pointer moves forward
            j--;
            // Loop the pointer back one bit to handle elements moving from behindk--; }}};Copy the code