Постановка задачи
Дан массив nums с n объектами красного, белого или синего цвета, отсортируйте их на месте так, чтобы объекты одного цвета были рядом , с цветами в порядке красный, белый и синий.
Мы будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего цветов соответственно.
Вы должны решить эту проблему, не используя библиотечную функцию сортировки.
Постановка задачи взята с: https://leetcode.com/problems/sort-colors
Пример 1:
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Пример 2:
Input: nums = [2, 0, 1]
Output: [0, 1, 2]
Пример 3:
Input: nums = [0]
Output: [0]
Пример 4:
Input: nums = [1]
Output: [1]
Ограничения:
- n == nums.length
- 1 <= n <= 300
- nums[i] is 0, 1, or 2
Объяснение
Простой подсчет
Простым подходом будет подсчет вхождений каждого целого числа 0, 1 и 2 с использованием трех разных переменных.
Используя указанные выше три переменные счетчика, мы заполняем массив.
Небольшой фрагмент C++ подхода будет выглядеть так:
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
count0++;
if (arr[i] == 1)
count1++;
if (arr[i] == 2)
count2++;
}
for (int i = 0; i < count0; i++)
arr[i] = 0;
for (int i = count0; i < (count0 + count1); i++)
arr[i] = 1;
for (int i = (count0 + count1); i < n; i++)
arr[i] = 2;
Временная сложность приведенной выше программы составляет O (N). Но в приведенном выше подходе мы повторяем массив дважды.
Проблема национального флага Нидерландов
Мы можем использовать подход проблемы голландского национального флага. Задача была поставлена с тремя цветами, здесь у нас 0, 1 и 2. Для решения этой задачи массив разбит на четыре секции.
Проверим алгоритм:
- Keep three indices low = 1, mid = 1 and, high = N and, there are four ranges,
1 to low (the range containing 0),
low to mid (the range containing 1),
mid to high (the range containing unknown elements) and
high to N (the range containing 2).
- Traverse the array from start to end and mid is less than high. (Loop counter is i)
- if element == 0
- swap the element with the element at index low and update low = low + 1 and mid = mid + 1
- if element == 1
- set mid = mid + 1
- if element == 2
- swap the element with the element at index high and update high = high – 1.
- set i = i – 1.
- return array
Временная сложность программы составляет O(N), так как мы итерируем массив только один раз. Сложность пространства составляет O(1), потому что мы не используем никаких других дополнительных структур данных.
Решение C++
class Solution {
public:
void sortColors(vector<int>& nums) {
int low = 0, mid = 0, high = nums.size() - 1;
while(mid <= high){
switch (nums[mid]){
case 0:
swap(nums[low++], nums[mid++]);
break;
case 1:
mid++;
break;
case 2:
swap(nums[mid], nums[high--]);
break;
}
}
}
};
Решение Golang
func sortColors(nums []int) {
low := 0
mid := 0
high := len(nums) - 1
for mid <= high {
switch (nums[mid]) {
case 0:
tmp := nums[low]
nums[low] = nums[mid]
nums[mid] = tmp
low++
mid++
break
case 1:
mid++
break
case 2:
tmp := nums[mid]
nums[mid] = nums[high]
nums[high] = tmp
high--
break
}
}
}
Решение для JavaScript
var sortColors = function(nums) {
function swap(i, j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
let low = 0;
let high = nums.length - 1;
let mid = 0;
while (mid <= high) {
const n = nums[mid];
if (n === 0) {
swap(mid, low);
low++;
mid++;
} else if (n === 2) {
swap(mid, high);
high--;
} else {
mid++;
}
}
};
Давайте решим проблему
Input: nums = [2, 0, 2, 1, 1, 0]
Step 1: low = 0
mid = 0
high = nums.length() - 1
= 6 - 1
= 5
Step 2: loop while mid < = high
0 <= 5
true
switch (nums[mid])
nums[mid] = nums[0]
= 2
case 2:
swap(nums[mid], nums[high--])
swap(nums[0], nums[5])
swap(2, 0)
nums = [0, 0, 2, 1, 1, 2]
high--
high = 4
Step 3: loop while mid < = high
0 <= 4
true
switch (nums[mid])
nums[mid] = nums[0]
= 0
case 0:
swap(nums[low++], nums[mid++])
swap(nums[0], nums[0])
swap(0, 0)
nums = [0, 0, 2, 1, 1, 2]
low++
mid++
low = 1
mid = 1
Step 4: loop while mid < = high
1 <= 4
true
switch (nums[mid])
nums[mid] = nums[1]
= 0
case 0:
swap(nums[low++], nums[mid++])
swap(nums[1], nums[1])
swap(1, 1)
nums = [0, 0, 2, 1, 1, 2]
low++
mid++
low = 2
mid = 2
Step 5: loop while mid < = high
2 <= 4
true
switch (nums[mid])
nums[mid] = nums[2]
= 2
case 2:
swap(nums[mid], nums[high--])
swap(nums[2], nums[4])
swap(2, 1)
nums = [0, 0, 1, 1, 2, 2]
high--
high = 3
Step 6: loop while mid < = high
2 <= 3
true
switch (nums[mid])
nums[mid] = nums[2]
= 1
case 1:
mid++
mid = 3
Step 7: loop while mid < = high
3 <= 3
true
switch (nums[mid])
nums[mid] = nums[3]
= 1
case 1:
mid++
mid = 4
Step 8: loop while mid < = high
4 <= 3
false
The result is [0, 0, 1, 1, 2, 2]
Первоначально опубликовано на https://alkeshghorpade.me.