题目
输入一个数组,将数组中奇数放到偶数前面
例子
oddEven([1,2,3,4,5]) -> [1,3,5,4,2]
假设
- 输入的数组不为空
tips
- 快速排序变形
答案
解法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
性能:
- 时间复杂度
O(n)
- 空间复杂度
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