75. Sort Colors

leetcode medium

#array#csharp#leetcode#medium#sort

Task

Дан массив nums, содержащий n объектов, окрашенных в красный, белый или синий цвет. Отсортируйте их на месте так, чтобы объекты одного цвета находились рядом, а цвета располагались в порядке красный, белый и синий.

Мы будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего цветов соответственно.

Вы должны решить эту задачу без использования функции сортировки библиотеки.

Пример:

Input: nums = [2,0,2,1,1,0]

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

C# solution

matched/original

public class Solution {
    public void SortColors(int[] nums) {
        var p0 = 0;
        var curr = 0;
        var p2 = nums.Length - 1;
        while (curr <= p2) {
            if (nums[curr] == 0) {
                int temp = nums[p0];
                nums[p0++] = nums[curr];
                nums[curr++] = temp;
            } else if (nums[curr] == 2) {
                int temp = nums[curr];
                nums[curr] = nums[p2];
                nums[p2--] = temp;
            } else
                curr++;
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public void SortColors(vector<int>& nums) {
        var p0 = 0;
        var curr = 0;
        var p2 = nums.size() - 1;
        while (curr <= p2) {
            if (nums[curr] == 0) {
                int temp = nums[p0];
                nums[p0++] = nums[curr];
                nums[curr++] = temp;
            } else if (nums[curr] == 2) {
                int temp = nums[curr];
                nums[curr] = nums[p2];
                nums[p2--] = temp;
            } else
                curr++;
        }
    }
}

Java solution

matched/original

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, curr = 0;
        int p2 = nums.length - 1;
        int tmp;
        while (curr <= p2) {
            if (nums[curr] == 0) {
                tmp = nums[p0];
                nums[p0++] = nums[curr];
                nums[curr++] = tmp;
            } else if (nums[curr] == 2) {
                tmp = nums[curr];
                nums[curr] = nums[p2];
                nums[p2--] = tmp;
            } else {
                curr++;
            }
        }
    }
}

JavaScript solution

matched/original

var sortColors = function (nums) {
    let p0 = 0,
        curr = 0;
    let p2 = nums.length - 1;
    while (curr <= p2) {
        if (nums[curr] == 0) {
            [nums[curr++], nums[p0++]] = [nums[p0], nums[curr]];
        } else if (nums[curr] == 2) {
            [nums[curr], nums[p2--]] = [nums[p2], nums[curr]];
        } else curr++;
    }
};

Python solution

matched/original

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        p0 = curr = 0
        p2 = len(nums) - 1

        while curr <= p2:
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1

Go solution

matched/original

func sortColors(nums []int) {
    p0, curr := 0, 0
    p2 := len(nums) - 1
    for curr <= p2 {
        if nums[curr] == 0 {
            nums[curr], nums[p0] = nums[p0], nums[curr]
            curr++
            p0++
        } else if nums[curr] == 2 {
            nums[curr], nums[p2] = nums[p2], nums[curr]
            p2--
        } else {
            curr++
        }
    }
}

Explanation

Algorithm

1️⃣

Инициализация крайней правой границы нулей: p0 = 0. Во время выполнения алгоритма nums[idx < p0] = 0.

2️⃣

Инициализация крайней левой границы двоек: p2 = n - 1. Во время выполнения алгоритма nums[idx > p2] = 2.

3️⃣

Инициализация индекса текущего элемента для рассмотрения: curr = 0.

Пока curr <= p2:

Если nums[curr] = 0: поменять местами элементы с индексами curr и p0, и сдвинуть оба указателя вправо.

Если nums[curr] = 2: поменять местами элементы с индексами curr и p2. Сдвинуть указатель p2 влево.

Если nums[curr] = 1: сдвинуть указатель curr вправо.

😎