剑指offer 12 --调整数组顺序，使奇数位于偶数前面

调整数组顺序，使奇数位于偶数前面

github地址

题目描述

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

牛客网题目入口

思路

• 需要注意到保证奇数和奇数、偶数和偶数的相对位置不变。

如果允许建新数组的话：

• 思路1：另开两个数组，扫一遍分别存偶数和奇数，然后将偶数连接到奇数后面
• 思路2：扫一遍统计奇数的个数，新建一个等长的数组，奇数从头往后加，偶数从奇数长度下标处往后加（当允许另开空间时，此方法较好）
• 思路3：扫一遍，遇到偶数就从列表中删除，然后追加到列表末端。需注意结束扫描的条件

如果只允许在原数组上做交换操作：

• 思路4：利用冒泡排序的思想，从前往后扫，遇到奇数就往前冒泡（或者从后往前扫，遇到偶数往后冒泡），不开辟额外空间

代码

#思路1

def reOrderArray(self, array):
        # write code here
        odd,even=[],[]
        for i in array:
            odd.append(i) if i & 0x1 ==1 else even.append(i)
        return odd+even

#思路4
class Solution:
    def reOrderArray(self, array):
       
        last_odd = -1
        for i in range(0, len(array)):
            if array[i] % 2 == 1:
                for j in range(i, last_odd+1, -1):
                    array[j], array[j-1] = array[j-1], array[j]
                    print(array)
                last_odd += 1
                print('last_odd is {}'.format(last_odd))
        return array  

S = Solution()

print(S.reOrderArray([-1, 2, -3, 4, -5, -6, 7, 8, 9, 10, -10]))


###result
last_odd is 0

[-1, -3, 2, 4, -5, -6, 7, 8, 9, 10, -10]
last_odd is 1

[-1, -3, 2, -5, 4, -6, 7, 8, 9, 10, -10]
[-1, -3, -5, 2, 4, -6, 7, 8, 9, 10, -10]
last_odd is 2

[-1, -3, -5, 2, 4, 7, -6, 8, 9, 10, -10]
[-1, -3, -5, 2, 7, 4, -6, 8, 9, 10, -10]
[-1, -3, -5, 7, 2, 4, -6, 8, 9, 10, -10]
last_odd is 3

[-1, -3, -5, 7, 2, 4, -6, 9, 8, 10, -10]
[-1, -3, -5, 7, 2, 4, 9, -6, 8, 10, -10]
[-1, -3, -5, 7, 2, 9, 4, -6, 8, 10, -10]
[-1, -3, -5, 7, 9, 2, 4, -6, 8, 10, -10]
last_odd is 4
[-1, -3, -5, 7, 9, 2, 4, -6, 8, 10, -10]

拓展

如果不要求奇数和偶数的相对位置不变，只要能奇数在前，偶数在后。可以类似于快排，在头和尾分别设置一个指针，头指针指向奇数则后移，尾指针指向偶数则前移。

class Solution:
    # 一个类似于快排的方法, 只是简单的满足了奇数在前,偶数在后, 奇数的顺序发生了改变
    def reOrderArray(self, array):
        if len(array) < 1:
            return
        elif len(array) == 1:
            return array

        front = 0
        rear = len(array)-1
        while front <= rear:
            while array[front] & 0x1 == 1:
                front += 1
            while array[rear] & 0x1 == 0:
                rear -= 1
            array[front], array[rear] = array[rear], array[front]

        array[front], array[rear] = array[rear], array[front]
        return array