输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
提示：
1 <= nums.length <= 50000
1 <= nums[i] <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解:
思路一：借助额外的存储空间
-
使用两个临时数组
-
一个存放偶数，一个存放奇数
-
最后把两个数组合并得到最终结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/**
*
* 暴力解法：
* 使用两个临时数组
* 一个存放偶数，一个存放奇数
* 最终把两个数据合并得到最终结果
*
* 时间复杂度 : O(N)
* 空间复杂度 : O(N)
*
* */
public int[] exchange(int[] nums) {
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (num % 2 == 0)
list2.add(num);
else
list1.add(num);
}
list1.addAll(list2);
int[] ans = new int[list1.size()];
for (int i = 0; i < list1.size(); i++) {
ans[i] = list1.get(i);
}
return ans;
}
|
复杂度分析:
- 时间复杂度 : O(N)
- 空间复杂度 : O(N)
思路二：头尾双指针
- 初始化两个指针
- 头指针指向数组起始位置
- 尾指针指向数据末尾位置
- left 一直向右移动，直到它碰到第一个偶数
- right 一直往左移动，直到它碰到第一个奇数
- 交换 left 和 right位置的元素，并把left 右移，right左移
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/**
*
* 双指针
* 头指针 left, 尾指针 right
* left一直往右移，直到它指向的值为偶数
* right一直往左移，直到它指向的数为奇数
* 交换 left 和 right位置的元素，并且left右移，right左移
*
* */
public void swap(int[] nums, int left ,int right){
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
public int[] exchange1(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right){
if (nums[left] % 2 == 1){
left ++;
continue;
}
if (nums[right] % 2 == 0){
right --;
continue;
}
swap(nums, left ++, right --);
}
return nums;
}
|
复杂度分析:
- 时间复杂度 : O(N)
- 空间复杂度 : O(1)
思路三：快慢指针
- 用两个指针
- slow指针指向最后一个偶数
- fast 遍历数组
- 当 fast 指向的数字时奇数时
- 交换 slow 和 fast的元素，并且slow ++
- 直至fast遍历完所有元素，则数组中所有的奇数都会排列在偶数之前
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/**
*
* 快慢指针
* 用两个指针，
* slow 指向最后一个偶数
* fast 遍历数组
* 当fast指向的数字是奇数时
* 交换 slow 和 fast的元素 并且 slow ++
* */
public int[] exchange2(int[] nums){
int slow = 0, fast = 0;
while (fast < nums.length){
if (nums[fast] % 2 == 1)
// 奇数时
swap(nums, slow ++, fast);
fast ++;
}
return nums;
}
|
复杂度分析
- 时间复杂度 : O(N)
- 空间复杂度 : O(1)
