剑指Offer.21-调整数组顺序使奇数位于偶数前面
剑指Offer.21-调整数组顺序使奇数位于偶数前面
题目链接
<剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode） (leetcode-cn.com)>
问题描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分
个人想法
开辟一个新的数组，对输入数组进行遍历，遇到奇数从数组左侧插入，否则从右侧进行插入。
时间复杂度：$O(N)$
空间复杂度：$ O(N)$
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int[] exchange(int[] nums) {
int[] res = new int[nums.length];
int left = 0;
int right = nums.length-1;
for(int i=0;i<nums.length;i++){
if(nums[i] % 2 == 0){
res[right] = nums[i];
right--;
}else{
res[left] = nums[i];
left++;
}
}
return res;
}
}
|
官方解法
使用双指针同时从左右两次向中间进行扫描，在左侧扫描到偶数，右侧扫描到奇数时，使用指针记录当前两元素的位置，交换两个元素，直到 $i=j$，与个人想法的差距在空间开销上，官解在原地上进行操作，没有额外的空间开销，但会对原始数据进行破坏
时间复杂度：$O(N)$
空间复杂度：$ O(1)$
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int[] exchange(int[] nums) {
int i = 0, j = nums.length - 1, tmp;
while(i < j) {
while(i < j && (nums[i] & 1) == 1) i++;
while(i < j && (nums[j] & 1) == 0) j--;
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
return nums;
}
}
|