Description

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 与 leetcode 283 类似
难度简单:
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

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

提示：

  1. 1 <= nums.length <= 50000

  2. 1 <= nums[i] <= 10000

    Solution

    双指针 + 双端扫描

    1. class Solution {
    2.  public int[] exchange(int[] nums) {
    3.      int left = 0, right = nums.length - 1;
    5.      while(left <= right){
    6.          while (left <= right && (nums[left] & 1) == 1) //寻找偶数，跳过奇数
    7.              left ++;
    8.          while( left <= right && (nums[right] & 1) == 0)  // 寻找奇数，跳过偶数
    9.              right --;
    10.          if (left <= right)  
    11.              swap(nums, left++, right--);
    12.      }
    13.      return nums;
    14.  }
    16.  private void swap (int[] nums, int i, int j){
    17.      int temp = nums[i];
    18.      nums[i] = nums[j];
    19.      nums[j] = temp;
    20.  }
    21. }

    执行结果：通过
    显示详情
    执行用时：2 ms, 在所有 Java 提交中击败了99.40%的用户
    内存消耗：46.3 MB, 在所有 Java 提交中击败了85.59%的用户

Solution2

双指针 + 单端扫描

  1. class Solution {
  2.     public int[] exchange(int[] nums) {
  3.         int left = 0, right = 0;
  4.         // 维护 [0, left) 是奇数
  5.         while (right < nums.length){ 
  6.             if ((nums[right] & 1) == 0)
  7.                 right ++;
  8.             else if ( (nums[right] & 1) == 1)
  9.                 swap(nums, left ++, right ++);
  10.         }
  11.         return nums;
  12.     }
  14.     private void swap (int[] nums, int i, int j){
  15.         int temp = nums[i];
  16.         nums[i] = nums[j];
  17.         nums[j] = temp;
  18.     }
  19. }