【剑指offer】14. 调整数组顺序使奇数位于偶数前面

题目描述

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

思路

《剑指offer》P102

注意，书上给出的题目是不考虑奇数、偶数各自之间的相对顺序的，但是牛客网上给出的要求是相对位置不变。

书上给出的解法是：设置两个指针，p1从前向后，p2从后向前移动，p1为偶数p2为奇数时则交换两数，直到两个指针相遇。

这个解法无法保证相对顺序不变。本题的思路是：

• 设置两个指针
• p1从前向后移动，遇到第一个偶数时停止
• p2从p1的后一个位置开始移动，遇到第一个奇数时停止
• 将p1到p2之间的偶数（除了p2）依次向后移动一位，将p2指向的奇数赋给p1位置。

code

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        if not array:
            return array
        i = 0
        j = 1
        nlen = len(array)
        while i < nlen - 1:
            # 找到第一个偶数
            while i < nlen - 1 and not self.isEven(array[i]):
                i += 1
            # 找到该偶数后面的第一个奇数
            if j < i + 1:
                j = i + 1
            while j < nlen and self.isEven(array[j]):
                j += 1
            if j == nlen:
                break
            # 将偶数全部移动到奇数后面
            odd = array[j]
            for t in range(j - 1, i - 1, -1):
                array[t+1] = array[t]
            array[i] = odd
        return array

    def isEven(self, number):
        if number % 2 == 0 or number == 0:
            return True
        else:
            return False

           

牛客网上的这个题有一个小坑，C++代码返回值为空，python解法是需要返回修改后的array的。