Leetcode 75 Sort colors
题意：荷兰国旗问题，给一个数组[0,0,2,1,0]，构造成[0,0,0,1,2]的形式，分成三块
https://leetcode.com/problems/sort-colors/description/
题解：
在任意时刻，i 左边的数都是 0，k 右边的数都是 2，而 i 到 j 之间的数都是 1。
想象有三个指针，
i
,
j
,
k
i, j, k
i,j,k 维护
[
0
,
i
)
[0,i)
[0,i)为0，维护$[i,j)为1，[j, nums.size()]为2
想象有三个指针在动，i代表起始位置，k代表末尾位置，j遍历整个数组，移动j，当j的值指向的数字为0，的时候那么跟i交换，移动的过程中j >=i
class Solution {
public:
void sortColors(vector<int>& nums) {
for(int i = 0, j = 0, k = nums.size()-1; k >= j;) {
if(!nums[j]) {
swap(nums[i++], nums[j++]);
} else if( nums[j] == 2) {
swap(nums[j],nums[k--]);
} else j++;
}
}
};
时间复杂度
O
(
n
)
O(n)
O(n)
空间复杂度
O
(
1
)
O(1)
O(1)
原文地址：https://blog.csdn.net/xxxmmc/article/details/143754697
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！