leetcode
- 数组标记法
C++：
class Solution {
public:
void sortColors(vector<int>& nums) {
std::vector<int> arrMarks = std::vector<int>(3, 0);
for ( int i = 0; i < nums.size(); ++i ) {
int value = nums[i];
if ( value < arrMarks.size() ) {
arrMarks[value] += 1;
}
}
std::vector<int> sortedNums;
for ( int i = 0; i < arrMarks.size(); ++i ) {
for ( int j = 0; j < arrMarks[i]; ++j ) {
sortedNums.push_back(i);
}
}
nums = sortedNums;
}
};
- 三指针
C++：
class Solution {
public:
void sortColors(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
int current = left;
while ( current <= right ) {
if ( nums[current] == 0 && current >= left ) {
std::swap(nums[current], nums[left]);
++left;
} else if ( nums[current] == 2 ) {
std::swap(nums[current], nums[right]);
--right;
} else {
++current;
}
}
}
};
- 双指针法
C++：
class Solution {
public:
void sortColors(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
for ( int i = 0; i <= right; ++i ) {
while ( i <= right && nums[i] == 2 ) {
std::swap(nums[i], nums[right]);
--right;
}
if ( nums[i] == 0 ) {
std:;swap(nums[i], nums[left]);
++left;
}
}
}
};
网友评论