Description
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
Solutions
最简单的解决办法是扫描两次数组分别找到奇数和偶数就可以了,当然这样肯定是不符合效率要求的:
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
if array is None:
return None
res = []
for item in array:
if item % 2 == 1:
res.append(item)
for item in array:
if item % 2 == 0:
res.append(item)
return res
虽然这样实现是可以完成任务,但是很明显是
然而如果要求奇数和偶数相对位置不变时比较难办,只考虑将奇数挪到前面,偶数挪到后面可以类似于插入排序的方式,用两个指针从两边往中间扫:
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
if array is None:
return None
n = len(array)
l = 0
r = n - 1
while l <= r:
while array[l] & 1 == 1 and l < n:
l += 1
while array[r] & 1 != 1 and r > 0:
r -= 1
if l < r:
tmp = array[l]
array[l] = array[r]
array[r] = tmp
return array
考虑到可拓展性,可以将 array[l] & 1 == 1
这个部分用一个函数代替,而这个函数以函数的形式传入:
def is_even(n):
return (n & 1) == 0
def reOrderArray(self, array, func):
if array is None:
return None
n = len(array)
l = 0
r = n - 1
while l <= r:
while (not func(array[l])) and l < n:
l += 1
while func(array[r]) and r > 0:
r -= 1
if l < r:
tmp = array[l]
array[l] = array[r]
array[r] = tmp
return array