75. Sort Colors

Given an array with n objects colored red, white or blue, sort them 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.

Do not use the library's sort function for this problem. The solution time must be linear.

75. Сортировка цветов

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

Числа 0, 1, 2 обозначают красный, белый и синий цвет.

Запрещено пользоваться встроенной функцией сортировки. Решение задачи должно быть линейным.

// C++

class Solution {

public:

void sortColors(vector<int>& nums) {

}

};

// Java

public class Solution {

public void sortColors(int[] nums) {

}

}

РЕШЕНИЕ

сортировка - подсчетом

Анализ алгоритма

Следует воспользоваться сортировкой подсчетом. В трех переменных подсчитаем количество красных, белых и синих объектов.

Реализация алгоритма

class Solution

{

public:

void sortColors(vector<int>& nums)

{

int i, cnt[3] = {0,0,0};

for(i = 0; i < nums.size(); i++)

cnt[nums[i]]++;

for(i = 0; i < cnt[0]; i++) nums[i] = 0;

for(i = cnt[0]; i < cnt[0] + cnt[1]; i++) nums[i] = 1;

for(i = cnt[0] + cnt[1]; i < cnt[0] + cnt[1] + cnt[2]; i++) nums[i] = 2;

}

};

Java реализация

class Solution

{

public void sortColors(int[] nums)

{

int i, cnt[] = {0,0,0};

for(i = 0; i < nums.length; i++)

cnt[nums[i]]++;

for(i = 0; i < cnt[0]; i++) nums[i] = 0;

for(i = cnt[0]; i < cnt[0] + cnt[1]; i++) nums[i] = 1;

for(i = cnt[0] + cnt[1]; i < cnt[0] + cnt[1] + cnt[2]; i++) nums[i] = 2;

}

}