Leetcode Python超琐碎笔记: 905-Sort Array By Parity

simoncos · · 331 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

问题地址,难度:Easy

若有错误之处请予以指正:)

问题描述

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:
1 <= A.length <= 5000
0 <= A[i] <= 5000

题意分析

把偶数奇数分成前后两部分输出,空间上in-place当然最好。

我的实现及调优过程

方法1:92 ms

暴力没什么好说的。

class Solution:
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        even = []
        odd = []
        for n in A:
            if n % 2 == 0:
                even.append(n)
            else:
                odd.append(n)
        return even + odd
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
方法2:92 ms

使用列表生成式代替for循环,并无卵用,估计测试集太小了。

class Solution:
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        return [x for x in A if x % 2 == 0] + [x for x in A if x % 2 > 0]
        
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
方法3:96 ms

In-place 方法,速度相当。直接在A上做手脚。取两个指针分别指头尾,取余后两个余数有四种情况,分别处理:

  • 前>后
  • 前<后
  • 前=后=0
  • 前=后=1
class Solution:
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        i, j = 0, len(A) - 1
        while i < j:
            i_re = A[i] % 2
            j_re = A[j] % 2
            # odd - even
            if i_re > j_re:
                A[i], A[j] = A[j], A[i]
                i += 1
                j -= 1
            # even - odd
            elif i_re < j_re: 
                i += 1
                j -= 1
            else:
                if i_re == 0:
                    i += 1
                else:
                    j -= 1
        return A
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
方法3-Golang版72 ms

刚好这两天在看Golang的基本语法,拿来耍下。快了一丢丢(居然还是个100%),然而我是完全不能理解那些Python下60多ms是怎么刷出来的啊啊啊,卒。

func sortArrayByParity(A []int) []int {
    i := 0
    j := len(A) - 1
    var i_re, j_re int
    for ; i<j ;{
        i_re = A[i] % 2
        j_re = A[j] % 2
        if i_re > j_re {
            c := A[i] //这里一开始还出了你懂的bug,我已经被Python惯坏
            A[i] = A[j]
            A[j] = c
            i += 1
            j -= 1
        } else if i_re < j_re { 
            i += 1
            j -= 1
        } else {
            if i_re == 0 { i += 1} else {
                j -= 1}
        }
    }
    return A
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:simoncos

查看原文:Leetcode Python超琐碎笔记: 905-Sort Array By Parity

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

331 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传