共计 921 个字符,预计需要花费 3 分钟才能阅读完成。
题面
输出一个整数数组,实现一个函数来调整该数组中数字的程序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半局部。
示例:
输出:nums = [1,2,3,4]
输入:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。提醒:
0 <= nums.length <= 50000 1 <= nums[i] <= 10000
原题链接
剖析
刚开始想到思路 1:
从前向后遍历数组,遇到奇数时,什么也不做;遇到偶数时,把该偶数删除,而后把该偶数放到数组前面
然而这种思路会 超时
上面剖析超时起因:
数组最大长度为 50000,思路 1 绝不仅仅是简略的遍历数组,工夫复杂度为 O(N),思路 1 还波及到数组的插入、删除,删除操作(erase)的复杂度就是 O(N),最坏状况下,工夫复杂度为 O(N2),太大。
接下来想到思路 2:
采纳双指针,left 指向数组首部,right 指向数组尾部,left 总体趋势向右挪动,right 总体趋势向左挪动
上面剖析这种思路不超时的起因:
只遍历数组一遍,工夫复杂度为 O(N)。
源代码(正文局部即为思路)
class Solution {
public:
vector<int> exchange(vector<int>& nums) {int len = nums.size();
int left = 0;
int right = len-1;
while(left<right){
// 左偶、右奇
if(nums[left]%2==0 && nums[right]%2==1){// 替换数组元素的操作其实很简略,工夫复杂度 O(1),空间复杂度 O(1)
int tmpL = nums[left];
int tmpR = nums[right];
nums[left] = tmpR;
nums[right] = tmpL;
left++;
right--;
}
// 左偶、右偶
if(nums[left]%2==0 && nums[right]%2==0){right--;}
// 左奇、右偶
if(nums[left]%2==1 && nums[right]%2==0){
left++;
right--;
}
// 左奇、右奇
if(nums[left]%2==1 && nums[right]%2==1){left++;}
}
return nums;
}
};
提交后果:
正文完