📗difficulty:Easy
🎯Tags:
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。
样例 1 :
输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。
注意:
1 <= nums.length <= 50000
1 <= nums[i] <= 10000
经典双指针。
一个指针 front
指向 nums
的头部,一个指针 back
指向 nums
的尾部。如果 nums[front]
为偶数,nums[back]
为奇数,那么就交换他们的值。
但是这样的代码,不能实现 更高阶 的作用,比如“数组后面是 3 的倍数,前面不是 3 的倍数。”也就是代码可重用性不高。
/**
* 《剑指 Offer》 面试题21. 调整数组顺序使奇数位于偶数前面
* 初级解法 即 不可重用的 方法
*
* @param nums
* @return
*/
public int[] exchange(int[] nums) {
int front = 0;
int back = nums.length - 1;
int tmp = 0;
while (front < back) {
while (front < back && nums[front] % 2 != 0) {
front++;
}
while (front < back && nums[back] % 2 == 0) {
back--;
}
tmp = nums[front];
nums[front] = nums[back];
nums[back] = tmp;
}
return nums;
}
- 时间复杂度:
O(n)
。每个元素遍历一次。 - 空间复杂度:
O(1)
。
基础思路并不难,主要考察对代码可重用性的实践。