i373.Partition_Array_by_Odd_and_Even.md

i373 · Partition Array by Odd and Even

Easy

https://www.lintcode.com/problem/373/

Description

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

The answer is not unique. All you have to do is give a vaild answer.

Example

Example 1:

Input: [1,2,3,4] Output: [1,3,2,4]

Example 2:

Input: [1,4,2,3,5,6] Output: [1,3,5,4,2,6]

Challenge

Do it in-place.

Tags

• Opposite Direction Two Pointers
• Two Pointers
• Array

Related Problems

• 31 Partition Array Medium

sol:

原题目很简单，只需要将原数组扫描两遍，第一遍加入奇数，第二遍加入偶数，然后把答案数组覆盖原数组即可。

对于challenge问题，我们需要采用双指针（two pointer）的方法，一个从头开始，一个从尾开始，头指针定位到从前到后的第一个偶数，尾指针定位到从后到前的第一个奇数，两者交换即可。直到尾指针在头之前前面。

python

class Solution:
    """
    @param: nums: an array of integers
    @return: nothing
    """
    def partitionArray(self, nums):
        # write your code here
        if not nums:
            return

        left, right = 0, len(nums) - 1
        while left <= right:
            while left <= right and nums[left] % 2 != 0:
                left += 1
            while left <= right and nums[right] % 2 == 0:
                right -= 1
                
            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1