跳至主要內容

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

ITCharge大约 1 分钟

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面open in new window

  • 标签:数组、双指针、排序
  • 难度:简单

题目链接

题目大意

描述:给定一个整数数组 numsnums

要求:将奇数元素位于数组的前半部分,偶数元素位于数组的后半部分。

说明

  • 0nums.length500000 \le nums.length \le 50000
  • 0nums[i]100000 \le nums[i] \le 10000

示例

  • 示例 1:
输入:nums = [1,2,3,4,5]
输出:[1,3,5,2,4] 
解释:为正确答案之一

解题思路

思路 1:快慢指针

定义快慢指针 slowslowfastfast,开始时都指向 00

  • fastfast 向前搜索奇数位置,slowslow 指向下一个奇数应当存放的位置。
  • fastfast 不断进行右移,当遇到奇数时,将该奇数与 slowslow 指向的元素进行交换,并将 slowslow 进行右移。
  • 重复上面操作,直到 fastfast 指向数组末尾。

思路 1:代码

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        slow, fast = 0, 0
        while fast < len(nums):
            if nums[fast] % 2 == 1:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1
            fast += 1

        return nums

思路 1:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 为数组 numsnums 中的元素个数。
  • 空间复杂度O(1)O(1)