剑指offer-68、调整数组顺序使奇数位于偶数前⾯(⼆)
题⽬描述输⼊⼀个⻓度为 n 整数数组，数组⾥⾯可能含有相同的元素，实现⼀个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前⾯部分，所有的偶数位于数组的后⾯部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。
数据范围：0 ≤ n ≤ 50000，数组中每个数的值 0 ≤ val ≤ 10000
要求：时间复杂度 O(n)，空间复杂度 O(1)
示例 1
输⼊：
返回值：
说明：或者也是正确答案
示例 2
输⼊：
返回值：
说明：等也是正确答案
思路及解答
两次遍历
第一次遍历收集奇数，第二次遍历收集偶数
这种方法虽然简单易懂，但需要额外空间，不符合题目要求
public class Solution {
public int[] reorderArray(int[] nums) {
if (nums == null || nums.length == 0) {
return new int;
}
int[] result = new int;
int index = 0;
// 第一次遍历：收集所有奇数
for (int num : nums) {
if (num % 2 == 1) {
result = num;
}
}
// 第二次遍历：收集所有偶数
for (int num : nums) {
if (num % 2 == 0) {
result = num;
}
}
return result;
}
}
[*]时间复杂度：O(n)
[*]空间复杂度：O(n)
双指针交换（推荐）
这道题需要奇数在⼀半，偶数在另外⼀半就可以，并没有要求他们之间的顺序，那么就可以⽤双指针，⼀个指针在左边，⼀个指针在右边，⽐如 1,3,5,6,7 :
左指针往右遍历直到找到偶数，也就是 6 停下来，
右指针往左⾛，直到找到第⼀个奇数，也就是 7 停下来。
两者交换:
左指针继续往右边⾛，两个指针相遇，结束，这个时候其实偶数已经全部在右边了。
这个例⼦⾥⾯只经过⼀次交换，如果是多次交换，那么结束的条件同样也是两个指针相遇。
public class Solution { public int[] reorderArray(int[] nums) { if (nums == null || nums.length 很好很强大我过来先占个楼 待编辑 谢谢分享，辛苦了 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 东西不错很实用谢谢分享 前排留名，哈哈哈 新版吗？好像是停更了吧。 过来提前占个楼 鼓励转贴优秀软件安全工具和文档！ 谢谢楼主提供！ yyds。多谢分享 收藏一下 不知道什么时候能用到 懂技术并乐意极积无私分享的人越来越少。珍惜
页:
[1]