首先这道题采用two points的方法,设置头指针i和尾指针j,然后先用i往后遍历找到偶数,j往前遍历找到偶数,
然后交换i,j所指向的值,同时需要将i++,j--
时间复杂度: O(n)
额外空间复杂度: O(1)
标程:
class Solution {
public:
/**
*
* @param number string字符串
* @return string字符串
*/
string change(string number) {
int len = number.size();
int i = 0, j = len - 1;
while (i < j) {
while (i < j && (number[i] - '0') & 1) i++;
while (i < j && (number[j] - '0') & 1) j--;
if (i < j) swap(number[i++], number[j--]);
}
return number;
}
};
京公网安备 11010502036488号