题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。
示例:
1 | 输入:nums = [1,2,3,4] |
提示:
- $0 <= nums.length <= 50000$
- $0 <= nums[i] <= 10000$
算法
(双指针,位运算)) $O(n)$
使用两个指针 $l、r$,$l$ 从前往后扫描找到偶数时停止,$r$ 从后往前扫描找到奇数时停止,此时如果 $l < r$ 则交换两个数,循环以上过程直到 $l >= r$ 为止。
小技巧:使用位运算和 $1$ 取 &
的结果判断是奇数还是偶数,在计算机中 $%$ 运算是非常慢的。
时间复杂度
$O(n)$
空间复杂度
$O(1)$
C++ 代码
1 | class Solution { |