刷题-排序4

题目：

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例：

输入：[4,2,5,7]

输出：[4,5,2,7]

解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

提示：

2 <= A.length <= 20000

A.length % 2 == 0

0 <= A[i] <= 1000

方法1：

思路：选择排序的变形。

定义 i=0 ,j=1;每次循环都加上2

A[i] 是求偶数

A[j]是奇数

代码如下：

class Solution(object):

    def sortArrayByParityII(self, A):

        """

        :type A: List[int]

        :rtype: List[int]

        """

        i = 0

        j = 1

        while i < len(A) and j < len(A):

            if A[i] % 2 == 0:

                i += 2

            else:

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

                j += 2

        return A

if __name__ == '__main__':

    res = Solution()

    rt = res.sortArrayByParityII([4,2,5,7])

    print(rt)

方法2：

定义两个空列表

一个放偶数，一个放奇数

然后重新调整A列表。2i放偶数，2i+1放奇数

代码如下：

class Solution(object):

    def sortArrayByParityII(self, A):

        """

        :type A: List[int]

        :rtype: List[int]

        """

        B = []

        C = []

        for i in A:

            if i % 2 == 0:

                B.append(i)

            if i % 2 != 0:

                C.append(i)

        for i in range(len(B)):

            A[i*2] = B[i]

            A[i*2+1] = C[i]

        return A

if __name__ == '__main__':

    res = Solution()

    rt = res.sortArrayByParityII([4,2,5,7])

    print(rt)

方法三：以内存换时间

思路：

用两个列表推导式，一个放偶数，一个放奇数

定义一个空列表

代码如下：

class Solution:

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

        B = [i for i in A if i % 2 != 0]

        C = [i for i in A if i % 2 == 0]

        D = []

        for B,C in zip(B,C):

            D.append(C)

            D.append(B)

        return D

if __name__ == '__main__':

    res = Solution()

    rt = res.sortArrayByParityII([4,2,5,7])

    print(rt)

用到的知识点：选择排序，列表推导式，zip()函数，