Partition Array by Odd and Even

Question

  1. Partition an integers array into odd number first and even number second.
  3. Example
  4. Given [1, 2, 3, 4], return [1, 3, 2, 4]
  6. Challenge
  7. Do it in-place.

题解

将数组中的奇数和偶数分开，使用『两根指针』的方法最为自然，奇数在前，偶数在后，若不然则交换之。

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: an array of integers
  4.      * @return: nothing
  5.      */
  6.     public void partitionArray(int[] nums) {
  7.         if (nums == null) return;
  9.         int left = 0, right = nums.length - 1;
  10.         while (left < right) {
  11.             // odd number
  12.             while (left < right && nums[left] % 2 != 0) {
  13.                 left++;
  14.             }
  15.             // even number
  16.             while (left < right && nums[right] % 2 == 0) {
  17.                 right--;
  18.             }
  19.             // swap
  20.             if (left < right) {
  21.                 int temp = nums[left];
  22.                 nums[left] = nums[right];
  23.                 nums[right] = temp;
  24.             }
  25.         }
  26.     }
  27. }

C++

  1.   void partitionArray(vector<int> &nums) {
  2.         if (nums.empty()) return;
  4.         int i=0, j=nums.size()-1;
  5.         while (i<j) {
  6.             while (i<j && nums[i]%2!=0) i++;
  7.             while (i<j && nums[j]%2==0) j--;
  8.             if (i != j) swap(nums[i], nums[j]);
  9.         }
  10.     }

源码分析

注意处理好边界即循环时保证left < right.

复杂度分析

遍历一次数组，时间复杂度为 O(n), 使用了两根指针，空间复杂度 O(1).