文章目录
剑指offer 21 调整数组顺序使奇数位于偶数前面 LeetCode 905
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：
nums = [1,2,3,4]
输出：
[1,3,2,4]
注：
[3,1,2,4] 也是正确的答案之一。
提示：
-
0 <= nums.length <= 50000
-
1 <= nums[i] <= 10000
解法一: 利用双指针
建立一个和
nums
长度一样的数组
res
,遍历
nums
,当当前元素是奇数时从前往后放，
left++
, 当当前元素是偶数时，从后往前放,
right--
。
class Solution {
public int[] exchange(int[] nums) {
if(nums == null || nums.length == 0) return 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[left++] = nums[i];
}else{//偶数从后往前放
res[right--] = nums[i];
}
}
return res;
}
}
解法二：快速排序思想
本质仍然是用到双指针的思想，但不需要额外的空间了，让
left
指向数组最左边，
right
指向数组最右边，
left
不断右移，直到指向的元素不是奇数时停下，
right
则向左边移动，直到指向的元素不是偶数时停下，然后交换两个指针指向的元素，在两个指针相遇之前，
left
指针总是位于
right
指针的前面,接着开始下一轮循环，退出循环的条件是
left>right
。实际上不难发现这其实就是快速排序思想中的一轮循环。
class Solution {
public int[] exchange(int[] nums) {
if(nums == null || nums.length == 0) return nums;
int left = 0;
int right = nums.length - 1;
while(left < right){
//这里left<nums.length的判断不能省，如全是奇数[1,3,5]，不写该条件，left将出现数组下标越界，right同理
while(left < nums.length && nums[left] % 2 != 0) left++;
while(right >= 0 && nums[right] % 2 == 0) right--;
/*这里的if判断也不能省，因为在交界处的时候，如[1,3,2,4]
经过上面两个while后，left指着2，right指着3，是不需要交换了的*/
if(left < right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
return nums;
}
}
扩展题：需要保证奇数和奇数，偶数和偶数之间的相对位置不变
需要保证奇数和奇数，偶数和偶数之间的相对位置不变，这和上面不太一样，上面的解法不能保证相对位置不变。例如对于
[1,2,3,4,5]
，调整后应该得到
[1,3,5,2,4]
，而不能是
[1,3,5,4,2]
这种相对位置改变的结果。
解题思路：
用到上面解法一的思路，但是需要先遍历数组计算出数组中奇数的个数
count
。而后不是将偶数从最后往前放了，而是从
count
的位置开始往后放，因为数组下标是从
0
开始的，
count
个奇数会占用前面
count-1
个下标的位置。
Java代码
class Solution {
public int[] exchange(int[] nums) {
if(nums == null || nums.length == 0) return nums;
int count = 0；
for(int num : nums){//求出数组中奇数的个数
if(num % 2 != 0){
count++;
}
}
int[] res = new int[nums.length];
int left = 0;
int right = count;
for(int i = 0;i < nums.length;i++){
if(nums[i] % 2 != 0){//奇数从前往后放
res[left++] = nums[i];
}else{//偶数从count处往后放
res[right++] = nums[i];
}
}
return res;
}
}