最直观的做法就是新开一个数组,然后奇数放奇数位,偶数放偶数位,时间复杂度O(N),空间复杂度O(N),代码如下:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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),常数空间。代码如下:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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