“对于程序员而言，刷了Leetcode不一定能拿offer，但是不刷肯定拿不到offer。”

Lusion鲁迅

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

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

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10000

---

Solutions

首尾双指针

1. 使用辅助数组：T(n) = O(n), V(n) = O(n)

算法（略）

优化： 采用位运算存储数据，T(n) = O(n), V(n) = O(1)

观察到1 <= nums[i] <= 10000 < 2^14 = 16384

class Solution{
  public int[] exchange(int[] nums) {
    if (nums == null) return null;
    int left = 0, right = nums.length-1;
    for (int i = 0;i<nums.length;i++) {
      if ((nums[i] & 1) == 0) {
        nums[right--] |= (nums[i]&16383)<<14;
      } else {
        nums[left++] |= (nums[i]&16383)<<14;
      }
    }
    for(int i = 0;i<nums.length;i++) {
      nums[i] >>= 14;
    }
    return nums;
  }
}

2. 采用快排思想：T(n) = O(n), V(n) = O(1)

class Solution{
  public int[] exchange(int[] nums) {
    if (nums == null) return null;
    int i = 0,j = nums.length-1;
    while (i < j) {
      while (i < j && (nums[i]&1) == 1) i++;
      while (i < j && (nums[j]&1) == 0) j--;
      int temp = nums[i];
      nums[i++] = nums[j];
      nums[j--] = temp;
    }
    return nums;
  }
}

快慢双指针

class Solution{
  public int[] exchange(int[] nums) {
    if (nums == null) return null;
    for (int i=0, j=0; j<nums.length; j++) {
      if((nums[j]&1)==1) {
      	int temp = nums[j];
        nums[j] = nums[i];
        nums[i++] = temp;
      }
    }
    return nums;
  }
}