Задача. Дан массив целых чисел. Значения могут быть только 0, 1 и 2. Нужно отсортировать на месте (без доп. памяти). Использовать библиотечные функции сортировки нельзя.
Например,
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Input: nums = [2,0,1]
Output: [0,1,2]
Ссылка на leetcode: https://leetcode.com/problems/sort-colors
Решение.
Решение разобрал тут: Задача с собеседования в Google: Sort Colors
Код решения:
public void sortColors(int[] nums) {
int left = 0;
int right = nums.length - 1;
int current = 0;
while (current <= right) {
if (nums[current] == 0) {
swap(nums, left, current);
left++;
current++;
} else if (nums[current] == 1) {
current++;
} else {
swap(nums, current, right);
right--;
}
}
}
private void swap(int nums[], int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}