黑马程序员技术交流社区

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

作者: 小蜀哥哥    时间: 2019-11-21 18:25
标题: 【成都校区】Python 算法题分析-按奇偶排序数组
本帖最后由 小蜀哥哥 于 2019-11-21 18:33 编辑

题目描述

给定⼀个⾮负整数数组 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