Sort Colors Problem Solution: Given an array nums
with n
objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0
, 1
, and 2
to represent the color red, white, and blue, respectively.
You must solve this problem without using the library’s sort function.
Example :
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Table of Contents
Sort Colors Problem Solution
Problem Solution In Python
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
curr = 0
for _ in range(len(nums)):
if nums[curr] == 0:
nums.pop(curr)
nums.insert(0, 0)
curr += 1
elif nums[curr] == 2:
nums.pop(curr)
nums.append(2)
else:
curr += 1
return
Problem Solution In Java
public void sortColors(int[] nums) {
int len = nums.length;
int zero=0,one=0,two=0;
for(int i=0;i<len;i++){
if(nums[i] == 0){
zero++;
}else if(nums[i]==1){
one++;
}else{
two++;
}
}
for(int i=0;i<zero;i++){
nums[i] = 0;
}
for(int i=zero;i<zero+one;i++){
nums[i] = 1;
}
for(int i=zero+one;i<len;i++){
nums[i] = 2;
}
}
Problem Solution In C++
class Solution {
public:
void sortColors(vector<int>& nums) {
int top = 0;
int bot = nums.size()-1;
int ct1 = 0;
int ct2 = 0;
while (top<=bot) {
if (nums[top] == 0) ct1++;
if (nums[top] == 1) ct2++;
top++;
}
for (int i = 0; i <= bot; i++) {
if (ct1-->0) nums[i] = 0;
else if(ct2-->0) nums[i] = 1;
else nums[i] = 2;
}
}
};
Problem Solution In C
void swap(int *a, int *b)
{
*a = *a^*b;
*b = *a^*b;
*a = *a^*b;
}
void sortColors(int* nums, int numsSize){
int zeros = 0, ones = 0, twos = numsSize - 1;
while (ones <= twos) {
if (nums[ones] == 0) {
if (ones != zeros)
swap(&nums[ones], &nums[zeros]);
ones++;
zeros++;
} else if (nums[ones] == 1) {
ones++;
} else {
if (twos != ones)
swap(&nums[twos], &nums[ones]);
twos--;
}
}
}