forked from larissalages/code_problems
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path75.cpp
More file actions
28 lines (28 loc) · 680 Bytes
/
75.cpp
File metadata and controls
28 lines (28 loc) · 680 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Problem 75. Sort Colors
// https://leetcode.com/problems/sort-colors/
// time complexity : O(n) only one traversal needed
// space complexity : O(1)
class Solution {
public:
void swap(int *x,int *y){
int temp=*x;
*x=*y;
*y=temp;
}
void sortColors(vector<int>& nums) {
int n=nums.size();
int low=0,mid=0,high=n-1;
while(mid<=high){
int x=nums[mid];
if(x==0){
swap(&nums[low++],&nums[mid++]);
}
else if(x==1){
mid++;
}
else if(x==2){
swap(&nums[mid],&nums[high--]);
}
}
}
};