План курса / Все задачи / Алгоритмы и структуры данных
Сортировка 012
легко
# решено
Дан массив colors, элементы которого представляют один из трех цветов: красный (0), зелёный (1) и синий (2). Необходимо отсортировать массив так, чтобы цвета шли в порядке: красный, зелёный, синий, и вернуть изменённый массив.
Важно, чтобы сортировка осуществлялась in-place, что означает выполнение сортировки без использования дополнительной памяти для копий массива.
Пример 1:
Ввод: colors = [2,1,1,0,0,1]
Вывод: [0,0,1,1,1,2]
Пример 2:
Ввод: colors = [2,2,2,2,0]
Вывод: [0,2,2,2,2]
Ограничения:
len(colors) >= 0
Элементы массива colors принимают значения 0, 1 или 2
from typing import *
def sort_012(colors: List[int]) -> List[int]:
# индекс: число, значение: кол-во повторений
count = [0 for _ in range(3)]
# делаем подсчет
for num in colors:
count[num] += 1
# сортируем
i = 0
for j in range(3):
for _ in range(count[j]):
colors[i] = j
i += 1
return colors
public class Solution {
public static List<int> Sort012(List<int> colors) {
// индекс: число, значение: кол-во повторений
int[] count = new int[3];
// делаем подсчет
foreach (int num in colors) {
count[num] += 1;
}
// сортируем
int i = 0;
for (int j = 0; j < 3; j++) {
for (int k = 0; k < count[j]; k++) {
colors[i] = j;
i += 1;
}
}
return colors;
}
}
package main
func sort012(colors []int) []int {
// индекс: число, значение: кол-во повторений
count := make([]int, 3)
// делаем подсчет
for _, num := range colors {
count[num]++
}
// сортируем
i := 0
for j := 0; j < 3; j++ {
for ; count[j] > 0; count[j]-- {
colors[i] = j
i++
}
}
return colors
}
import java.util.*;
public class Solution {
public List<Integer> sort012(List<Integer> colors) {
// индекс: число, значение: кол-во повторений
int[] count = new int[3];
// делаем подсчет
for (int num : colors) {
count[num]++;
}
// сортируем
int i = 0;
for (int j = 0; j < 3; j++) {
for (int k = 0; k < count[j]; k++) {
colors.set(i, j);
i++;
}
}
return colors;
}
}
from typing import *
def sort_012(colors: List[int]) -> List[int]:
# индекс: число, значение: кол-во повторений
count = [0 for _ in range(3)]
# делаем подсчет
for num in colors:
count[num] += 1
# сортируем
i = 0
for j in range(3):
for _ in range(count[j]):
colors[i] = j
i += 1
return colors
/**
* @param {number[]} colors
* @returns {number[]}
*/
export function sort012(colors) {
// индекс: число, значение: кол-во повторений
const count = [0, 0, 0];
// делаем подсчет
for (const num of colors) {
count[num] += 1;
}
// сортируем
let i = 0;
for (let j = 0; j < 3; j++) {
for (let _ = 0; _ < count[j]; _++) {
colors[i] = j;
i += 1;
}
}
return colors;
}