JZ21-调整数组顺序使奇数位于偶数前面（一）

发表于 分类于 本文字数： 357 阅读时长 ≈ 1 分钟

JZ21 调整数组顺序使奇数位于偶数前面（一）

描述

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

数据范围：$0≤n≤5000$，数组中每个数的值 $0≤val≤10000$

要求：时间复杂度 $O(n)$，空间复杂度 $O(n)$

进阶：时间复杂度 $O(n2)$，空间复杂度 $O(1)$

示例1

1
2
输入：[1,2,3,4]
返回值：[1,3,2,4]

示例2

1
2
输入：[2,4,6,5,7]
返回值：[5,7,2,4,6]

示例3

1
2
输入：[1,3,5,6,7]
返回值：[1,3,5,7,6]

题解

首先是简单暴力的方法，开两个新数组分别存奇偶数，遍历一遍找出来，再分别放进答案里就好。

然后是动点脑瓜子的方法，由于冒泡是稳定的，也就是说冒泡排序可以控制前后关系不变，我们只需要把冒泡排序的大小比较改成奇偶比较即可。

1
2
3
4
5
6
7
8
class Solution:
    def reOrderArray(self , array ):
        # 不定义新空间的话，用冒泡
        for i in range(len(array)-1, -1, -1):# 反向遍历，安全删除，不会导致索引问题，
            for j in range(i):
                if(array[j] %2 == 0 and array[j+1] % 2 != 0):
                    array[j], array[j+1] = array[j+1], array[j]
        return array