Saturday, October 20, 2018

[LeetCode]Sort Array By Parity II


最直观的做法就是新开一个数组,然后奇数放奇数位,偶数放偶数位,时间复杂度O(N),空间复杂度O(N),代码如下:

class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& A) {
int len = A.size(), i = 0, j = 1;
vector<int> res(len, 0);
for(const auto& a : A)
{
if(a % 2)
{
res[j] = a;
j += 2;
}
else
{
res[i] = a;
i += 2;
}
}
return res;
}
};

我们还可以不另外开数组,用双指针,一个指针每次查偶数位不合法的元素,另一个指针查奇数位的,如果存在我们就switch。时间复杂度O(n),常数空间。代码如下:


class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& A) {
int len = A.size(), i = 0, j = 1;
while (i < len && j < len)
{
while (i < len && A[i] % 2 == 0)i += 2;
while (j < len && A[j] % 2)j += 2;
if (i >= len || j >= len)break;
swap(A[i], A[j]);
}
return A;
}
};

No comments:

Post a Comment