剑指offer21:调整数组顺序使奇数位于偶数前面 python

题目描述解法

题目描述

解法

最容易想到的方法就是定义两个临时列表分别存储奇数和偶数 class Solution: def exchange(self, nums: List[int]) -> List[int]: nums1 = [] nums2 = [] for ele in nums: if ele % 2 == 1: nums1.append(ele) else: nums2.append(ele) return nums1+nums2

时间复杂度是O(n)， 空间复杂度为O(n).

双指针法 分别设置头指针i和尾指针j头指针指向奇数时，i += 1， 指向偶数时不动，等待尾指针，尾指针指向偶数时，j -= 1。如果头指针指向偶数，尾指针指向奇数，则交换两者。nums[i], nums[j] = nums[j], nums[i]。同时 i += 1，j -= 1。当i >= j时退出循环 class Solution: def exchange(self, nums: List[int]) -> List[int]: i, j = 0, len(nums)-1 while i<j: if nums[i] % 2 == 0 and nums[j] % 2 == 1: nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1 if nums[i] % 2 == 1: i += 1 if nums[j] % 2 == 0: j -= 1 return nums

时间复杂度是O(n)，空间复杂度是O(1)