算法随笔_26: 按奇偶排序数组

上一篇:算法随笔_25:长按键入-CSDN博客

=====

题目描述如下:

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的任一数组作为答案。

示例 1：

输入：nums = [3,1,2,4]
输出：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

=====

算法思路:

题目要求将 nums 中的的所有偶数元素移动到数组的前面，奇数元素放到后面。简单的想法就是我们可以开辟一个同样大小空间的数组，先把所有的偶数依次放入新数组，然后把剩下的奇数依次放入新数组的后半部分。

但这里我们使用了一个更高效的算法，无需开辟新的数组空间，仅仅使用了一个常数空间。一些其他的算法题当中，题目常常要求使用常数空间，即，O(1) 的空间复杂度。

我们这样来考虑，我们需要把后面的偶数放到前面来，那前面需要有一个空格子可以容纳后面的这个偶数。那必然需要先从前面移走一个元素。移走哪个元素呢？如果前面是个偶数，它本来就符合条件，我们无需移动它。因此，我们需要把一个奇数移动到后面去。后面的偶数移动到前面，前面的奇数移动到后边，我们把两个步骤合二为一，那就是把他们两个元素交换一下即可。具体的算法如下:

1. 我们设两个指针p1和p2，p1=0，p2=1。

2. 我们使用这两个指针枚举数组中的每一个元素。会有如下的情形:

   a. 如果当前p1指向的元素是偶数，无需移动，所以我们把p1指针向右移动一格。

   b.  如果当前p1指向的元素是奇数，由于我们需要在后面找一个偶数与它交换，所以我们判断当前p2所指的元素是否是偶数。如果是偶数，我们交换p1和p2所指的元素。然后我们把p1指针向右移动一格。

把p2指针向右移动一格，然后重复步骤2。

当p2到达数组末尾的时候，退出循环，算法结束。此时所有的偶数都排到了前面，后面紧跟奇数。

此算法的时间复杂度是O(n) 。空间复杂度是O(1)。

下面是代码实现:

class Solution(object):
    def sortArrayByParity(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        p1=0
        p2=1
        nums_len=len(nums)
        tmp=0
        while p2 < nums_len:
            if nums[p1]%2==0:
                p1+=1
            elif nums[p2]%2==0:
                tmp=nums[p1]
                nums[p1]=nums[p2]
                nums[p2]=tmp
                p1+=1
                
            p2+=1
        return nums