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

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

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

数据范围：0≤n≤5000，数组中每个数的值 0≤val≤10000 要求：时间复杂度 O(n)，空间复杂度 O(n) 进阶：时间复杂度 O(n^2)，空间复杂度 O(1)

思路：题目很简单，方法一：定义两个数组，一个存奇数，一个存偶数，然后合并两个数组。方法二：在原数组的基础上修改，找到一个奇数就把这个奇数往前挪，所以需要记录当前有多少个奇数，如果当前有k个奇数，那接下来找到的奇数原本在array[i]则需要挪到array[k]上，而array[k]-array[i-1]需要后移一位，挪到array[k+1]-array[i]

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def reOrderArray(self , array: List[int]) -> List[int]:
        # write code here
        #解法一：时间复杂度O(n),空间复杂度O(n)
#         if len(array) <= 1:
#             return array
#         arrSingle = []
#         arrDouble = []
#         for i in array:
#             if i % 2 == 1:
#                 arrSingle.append(i)
#             else :
#                 arrDouble.append(i)
#         return arrSingle + arrDouble
        #解法二：时间复杂度O(n^2),空间复杂度O(1)
        if len(array) <= 1:
            return array
        k = 0
        for i in range(0,len(array)):
            if array[i] % 2 == 1:
                c = array[i]
                for j in range(i-1,k-1,-1):
                    array[j+1] = array[j]
                array[k] = c
                k += 1
        return array