“This is the fifth day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

The title

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.

Example 1

Input: nums = [2,0,2,1, 0] output: [0,0,1,1,2,2]Copy the code

Example 2

Input: nums = [2,0,1] output: [0,1,2]Copy the code

Train of thought

At first glance, it looks like a simple sorting problem, and the only thing they’re asking for is sort in place, making changes to the array that’s passed in, not by returning a new variable.

When sorting an array, it’s easy to think of bubble sort:

Bubble sort code

    / * * *@param {number[]} nums
     * @return {void} Do not return anything, modify nums in-place instead.
     */
    var sortColors = function (nums) {
        const n = nums.length;

        if(n < 2) return;

        let temp;
        for(let i = 0; i < n; i++) {
            for(let j = i + 1; j < n; j++) {

                // Put the value of the larger value back
                if(nums[i] > nums[j]) { temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}}};Copy the code

The time complexity of bubble sort algorithm is O(n ^ 2), which is a relatively stable algorithm, but the efficiency is not very high

The use of Array. Sort

For sorting arrays, the prototype Array also provides a sort method, which takes a comparison function fn. If fn returns a value less than 0, a is placed before B, and if fn returns a value greater than 0, it does not transform. Sort also sorts arrays in place and does not copy them.

    nums.sort((a, b) = > a - b);
Copy the code

Double pointer + traversal

Bubble and sort are common algorithms, but in this case, there are only 0, 1, and 2 numbers in the array; All we need to do is put 0 at the top and 2 at the bottom, and when we’re done, the original array is sorted according to the problem

Concrete implementation:

  • Define left as the right boundary of header 0, right as the left boundary of tail 2, and index as the current traversal index

  • Left = index = 0, right = nums. length-1;

  • When index <= right, the loop is entered

    • If the currentnums[index] === 0That will beNums [left] interacts with nums[index] and sets left++, index++
    • If the currentnums[index] === 1That will beindex++, no switch operation is required
    • If the currentnums[index] === 2That will beNums [right] interacts with nums[index] and sets right--Here you can’tindex++Because thenums[right]Also may be2

  • When the loop ends, numS sorting is complete

Full code implementation

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

        // Define the exchange method and deconstruct the assignment
        const swap = (i, j) = > {
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }

        while(index <= right) {
            if(nums[index] === 0) {
                // Swap the 0 to the front
                swap(index, left);
                index++;
                left++;
            } else if(nums[index] == 1) {
                // Do not swap
                index++;
            } else {
                // Switch the 2 to the back
                // index++ cannot be set because nums[right] may also be 2swap(index, right); right--; }}};Copy the code

The time complexity of the above code is O(n) at most, and the sorting can be completed by completing the loop at most once

summary

Some ideas, such as bubble sort, is suitable for most cases can be carried out, but his performance, efficiency is generally not very good. For this problem, there are only three elements in numS analysis. Some operations can be performed on numS to improve the efficiency of the solution.

# LeetCode 👉 HOT 100 👉

Collection: LeetCode 👉 HOT 100, will update when you are free, we support a lot, click a like 👍

If you have a good solution or find something wrong with this article, please leave a comment at 😄