Luffy: Color classification

Topic describes

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.

Their thinking

algorithm

A double pointer, p0 indicates where the next 0 will be placed and p2 indicates where the next 2 will be placed

Train of thought

The key here is the loop invariants, the conditions that we need to follow in the loop.

First, we need an I to hold the traversal index in addition to the double pointer

The cyclic invariant of ontology is:

[0, p0) = 0

[p0, i] = 1

(p2, r) = 2

Where r is the right edge of our array. In the code, we replace it with nums. length-1 so that p0 and p2 are not pointing to 0,2

We exchange nums[I], nums[p0], or nums[I], nums[p2]. The loop terminates when I <= p2

The key to this condition is whether or not we need to add this =

Let’s look at a situation like this

2(p0, i), 0, 1(p2)

First the elements of I and P2 are swapped ➡️ 1(I, P0), 0(p2), 2

I ++ ➡️ 1, 0 (I, p2), 2 loop exit

Obviously, the array is not required, so the loop terminates with I <= p2 under the current loop invariant

code

/ * * *@param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let p0 = 0, p2 = nums.length - 1, i = 0

    // loop invariant
    /** [0, p0) = 0 [p0, i] = 1 (p2, num.length - 1) = 2 */

    while (i < p2) {
        if (nums[i] === 1) {
            i++
        } else if (nums[i] === 0) {
            ;[nums[p0], nums[i]] = [nums[i], nums[p0]]
            p0++
            i++
        } else if (nums[i] === 2) {
            ;[nums[p2], nums[i]] = [nums[i], nums[p2]]
            p2--
        }
    }
};
Copy the code