剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

用到 位运算 知识点;

• (nums[i]&1)==1 奇数判断，原理：奇数的最低位为1

描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

链接

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode） (leetcode-cn.com)

解法一：双指针,可以实现 原地交换

 1 class Solution {
 2     public int[] exchange(int[] nums) {
 3         int left = 0, right = nums.length - 1;
 4         while (left < right) {
 5             //  目标： 奇数在前，偶数在后
 6             // 如果为奇数，往前进一位
 7             while (left < right && (nums[left] & 1) == 1 ) {
 8                 left++;
 9             }
10 
11             // 如果为偶数，后退一位
12             while (left < right && (nums[right] & 1) == 0) {
13                 right--;
14             }
15             
16             // 此时，left侧 是 偶数，right侧 是 奇数，交换
17             int tmp = nums[left];
18             nums[left] = nums[right];
19             nums[right] = tmp; 
20         }
21         return nums;
22     }
23 }

解法二： 双端队列 （不推荐，输出的时候 Deque 需要转成 int[] 输出，很麻烦）

 1 class Solution {
 2     public int[] exchange(int[] nums) {
 3         Deque tmp = new ArrayDeque();
 4         for (int num:nums) {
 5             if((num & 1) == 1){
 6                 tmp.addFirst(num);
 7             }
 8             else {
 9                 tmp.addLast(num);
10             }
11         }
12         int[] arr2 = Arrays.stream(tmp.toArray(new Integer[]{})).mapToInt(Integer::valueOf).toArray();
13         return arr2;
14     }
15 }

参考

调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode） (leetcode-cn.com)