LeetCode Problem
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.
Solution
The first solution came out my mind definitely was Bubble Sort – Bubble sort – Wikipedia
That is a easy way to sort a array
C# Solution
Solution1 – bubble sort
public class Solution {
public void SortColors(int[] nums) {
int n = nums.Length;
while(n>1)
{
n--;
for(int i =0;i<nums.Length-1;i++)
{
if(nums[i] > nums[i+1])
{
int tmp = nums[i];
nums[i] = nums[i+1];
nums[i+1] = tmp;
}
}
}
}
}Time Complexity : O(n2)
Solution2
public class Solution {
public void SortColors(int[] nums) {
int a = 0;
int b = 0;
int c = 0;
//1.iterate and count each color
foreach(int num in nums)
{
switch(num)
{
case 0:
a+=1;
break;
case 1:
b+=1;
break;
case 2:
c+=1;
break;
}
}
//2.rewrite array
int cnt = 0;
while(a>0)
{
nums[cnt] = 0;
a--;
cnt++;
}
while(b>0)
{
nums[cnt] = 1;
b--;
cnt++;
}
while(c>0)
{
nums[cnt] = 2;
c--;
cnt++;
}
}
}Time Complexity : O(n)
We can found out there are just three color int this problem, so another way to solve this problem is to set three variables to store count of each color.
Java Solution
Solution1
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
while(n>1)
{
n--;
for(int i =0;i<nums.length-1;i++)
{
if(nums[i] > nums[i+1])
{
int tmp = nums[i];
nums[i] = nums[i+1];
nums[i+1] = tmp;
}
}
}
}
}Time Complexity : O(n2)
Runtime : 12ms、4ms、4ms
⭐Solution2
class Solution {
public void sortColors(int[] nums) {
int a = 0;
int b = 0;
int c = 0;
//1.iterate and count each color
for(int num : nums)
{
switch(num)
{
case 0:
a+=1;
break;
case 1:
b+=1;
break;
case 2:
c+=1;
break;
}
}
//2.rewrite array
int cnt = 0;
while(a>0)
{
nums[cnt] = 0;
a--;
cnt++;
}
while(b>0)
{
nums[cnt] = 1;
b--;
cnt++;
}
while(c>0)
{
nums[cnt] = 2;
c--;
cnt++;
}
}
}Time Complexity : O(n)
Runtime : 0ms、0ms、0ms
Python3 Solution
Solution1
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
while(n>1):
n-=1
for i in range(len(nums)-1):
if(nums[i] > nums[i+1]):
tmp = nums[i]
nums[i] = nums[i+1]
nums[i+1] = tmpSolution2
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
a = 0
b = 0
c = 0
for num in nums:
if num == 0:
a+=1
elif num == 1:
b+=1
else:
c+=1
cnt = 0
while(a>0):
nums[cnt] = 0
a-=1
cnt+=1
while(b>0):
nums[cnt] = 1
b-=1
cnt+=1
while(c>0):
nums[cnt] = 2
c-=1
cnt+=1JavaScript Solution
Solution1
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
var n = nums.length;
while(n>1)
{
n--;
for (let i=0; i<nums.length-1; i++) {
if(nums[i] > nums[i+1])
{
let tmp = nums[i];
nums[i] = nums[i+1];
nums[i+1] = tmp;
}
}
}
};Solution2
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
var a = 0;
var b = 0;
var c = 0;
nums.forEach(function(num){
switch(num)
{
case 0:
a+=1;
break;
case 1:
b+=1;
break;
case 2:
c+=1;
break;
}
});
var cnt = 0;
while(a>0)
{
nums[cnt] = 0;
a--;
cnt++;
}
while(b>0)
{
nums[cnt] = 1;
b--;
cnt++;
}
while(c>0)
{
nums[cnt] = 2;
c--;
cnt++;
}
};Conclusion
🧡If my solution helps, that is my honor!
🧡You can support me by clicking some ad, Thanks a lot
✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)
The problem link : Sort Colors – LeetCode
Latest Post