Partition Array by Odd and Even

Question

Partition an integers array into odd number first and even number second.

Example
Given [1, 2, 3, 4], return [1, 3, 2, 4]

Challenge
Do it in-place.

Solution

Use two pointers to keep the odd before the even, and swap when necessary.

Java

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: nothing
     */
    public void partitionArray(int[] nums) {
        if (nums == null) return;

        int left = 0, right = nums.length - 1;
        while (left < right) {
            // odd number
            while (left < right && nums[left] % 2 != 0) {
                left++;
            }
            // even number
            while (left < right && nums[right] % 2 == 0) {
                right--;
            }
            // swap
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
    }
}

C++

void partitionArray(vector<int> &nums) {
      if (nums.empty()) return;

      int i=0, j=nums.size()-1;
      while (i<j) {
          while (i<j && nums[i]%2!=0) i++;
          while (i<j && nums[j]%2==0) j--;
          if (i != j) swap(nums[i], nums[j]);
      }
  }

Src Code Analysis

Be careful not to forget left < right in while loop condition.

Complexity

To traverse the array, time complexity is O(n)O(n). And maintaining two pointers means O(1)O(1) space complexity.

results matching ""

    powered by

    No results matching ""