Description

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

Solutions

最简单的解决办法是扫描两次数组分别找到奇数和偶数就可以了,当然这样肯定是不符合效率要求的:

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        if array is None:
            return None
        res = []
        for item in array:
            if item % 2 == 1:
                res.append(item)
                
        for item in array:
            if item % 2 == 0:
                res.append(item)
        return res

虽然这样实现是可以完成任务,但是很明显是

然而如果要求奇数和偶数相对位置不变时比较难办,只考虑将奇数挪到前面,偶数挪到后面可以类似于插入排序的方式,用两个指针从两边往中间扫:

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        if array is None:
            return None
        
        n = len(array)
        l = 0
        r = n - 1
        while l <= r:
            while array[l] & 1 == 1 and l < n:
                l += 1
            while array[r] & 1 != 1 and r > 0:
                r -= 1
            
            if l < r:
                tmp = array[l]
                array[l] = array[r]
                array[r] = tmp
        return array

考虑到可拓展性,可以将 array[l] & 1 == 1 这个部分用一个函数代替,而这个函数以函数的形式传入:

def is_even(n):
  return (n & 1) == 0

def reOrderArray(self, array, func):
  if array is None:
            return None
        
        n = len(array)
        l = 0
        r = n - 1
        while l <= r:
            while (not func(array[l])) and l < n:
                l += 1
            while func(array[r]) and r > 0:
                r -= 1
            
            if l < r:
                tmp = array[l]
                array[l] = array[r]
                array[r] = tmp
        return array

References

  1. 014. 调整数组顺序使奇数位于偶数前面