pythontip 100days-day19

题目

输入一个数组,将数组中奇数放到偶数前面

例子

oddEven([1,2,3,4,5]) -> [1,3,5,4,2]

假设

  1. 输入的数组不为空

tips

  1. 快速排序变形

答案

解法1

def oddEven(nums):
    i = -1;
    for j in range(len(nums)):
        if nums[j] % 2 == 1:
            i += 1
            nums[i],nums[j] = nums[j],nums[i]
    return nums

性能

  1. 时间复杂度O(n)
  2. 空间复杂度O(1)

关键点:1.快速排序变形

解法2:

def oddEven(nums: list) -> list:
    if not nums:
        return nums
    i, j = 0, len(nums) - 1
    while i <= j:
        while nums[i] % 2 == 1 and i < len(nums):
            i += 1
        while nums[j] % 2 == 0 and i >= 0:
            j -= 1
        if i <= j:
            nums[i], nums[j] = nums[j], nums[i]


    return nums