Skip to content

Latest commit

 

History

History
70 lines (48 loc) · 1.53 KB

i373.Partition_Array_by_Odd_and_Even.md

File metadata and controls

70 lines (48 loc) · 1.53 KB

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