黑马程序员技术交流社区

标题: 【成都校区】Python 算法题分析-按奇偶排序数组 [打印本页]

---

作者: 小蜀哥哥    时间: 2019-11-21 18:25
标题: 【成都校区】Python 算法题分析-按奇偶排序数组


题目描述

给定⼀个⾮负整数数组 A，返回⼀个数组，在该数组中，A 的所有偶数元素之后跟着所有奇数元素。你可以返回满⾜此条件的任何数组作为答案。

示例
输⼊：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。

提示
1 <= A.length <= 5000 0 <= A<= 5000
方法一
想法和算法⾸先定义两个空列表 odd 和 even ，然后遍历整个列表，将列表中的奇数元素放⼊ odd 列表中，偶 数元素放⼊ even 列表中，然后将两个列表相加并返回。

实现

[Python] 纯文本查看 复制代码

class Solution:

    def sortArrayByParity(self, A: List[int]) -> List[int]:

        odd = []

        even = []

        for a in A:

            if a % 2 == 0:

                even.append(a)

            else:

                odd.append(a)

        return even + odd

复杂度分析
时间复杂度： O(N) ，其中 N 是列表 A 的⻓度；
空间复杂度： O(N)

有没有什么⽅法能让算法的空间复杂度为 O(1) ？

方法二
想法如果希望原地排序，可以使⽤快排，⼀个经典的算法。

算法
维护两个指针 i 和 j ，保证循环不变量：
    1. 对于任意索引⼩于 i 的元素都是偶数；
    2. 对于任意索引⼤于 j 的元素都是奇数。
从⽽，( A % 2 ， A[j] % 2 )的值有4中情况需要处理：
    1. 如果为(0, 1)，那么 i++,  j--；
    2. 如果为(1, 0)，那么交换 i 和 j；
    3. 如果为(0, 0)，那么说明 i 的位置是正确的，只能 i++;
    4. 如果为(1, 1)，那么说明 j 的位置是正确的，只能 j--;
通过这4种情况，可以保证 j-i 的值可以不断缩⼩，最终就可以得到奇偶有序的数组。

实现

[Python] 纯文本查看 复制代码

class Solution:

    def sortArrayByParity(self, A: List[int]) -> List[int]:

        i = 0

        j = len(A) - 1

        while i < j:

            # 必须先进⾏交换，再做判断进⾏ i 和 j 的运算，否则会导致多循环⼀次，中间的两个数错误

            if A % 2 == 1 and A[j] % 2 == 0:

                A, A[j] = A[j], A

            if A % 2 == 0:

                i = i + 1

            if A[j] % 2 == 1: 

                j = j - 1

        return A

复杂度分析
时间复杂度： O(N) ，其中 N 是列表 A 的⻓度，循环的每⼀步都让 j-i ⾄少减少了 1;
空间复杂度： O(1) ，不需要额外空间。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2