调整数组顺序使奇数位于偶数前面(一)

调整数组顺序使奇数位于偶数前面(一)_牛客题霸_牛客网

问题简述

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

要求：空间复杂度 O(1)

思路

• 定义 i 表示下一个奇数插入的位置，初始化 i=0；

• 从左往右遍历，假设在 j 位置找到一个奇数，保存至 tmp，则将 arr[i:j) 之间的数后移一位；

• 然后置 arr[i] = tmp, i += 1

Python

class Solution:
    def reOrderArray(self , arr: List[int]) -> List[int]:
        
        i = 0
        for j in range(len(arr)):
            if arr[j] & 1:  # 是奇数
                tmp = arr[j]  # 保存当前奇数
                # 把 arr[i:j] 后移一位
                for k in range(j - 1, i - 1, -1):
                    arr[k + 1] = arr[k]
                # 把当前奇数放到 i 位置
                arr[i] = tmp
                i += 1
                
        return arr