说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。
题目来源
- 分类：数组
- 调整数组顺序使奇数位于偶数前
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
题目分析
1. 不考虑约束条件（奇数和奇数，偶数和偶数之间的相对位置不变）
直接使用两个指针：第一个指针初始化时指向数组的第一个数字，第二个指针指向数组最后一个数字；第一个指针总是位于第二个指针前面，如果第一个指针指向的数字时偶数，并且第二个指针指向奇数，则交换这两个数字。实现如下：
function reOrderArray($array)
{
if ($array == null || count($array) <= 0) {
return [];
}
$pBegin = 0;
$pEnd = count($array) - 1;
while ($pBegin < $pEnd) {
// 向后移动，直到指向的是偶数
while ($pBegin < $pEnd && ($array[$pBegin] & 0x1) != 0) {
$pBegin++;
}
// 向前移动，直到指向的是奇数
while ($pBegin < $pEnd && ($array[$pEnd] & 0x1)== 0) {
$pEnd--;
}
if($pBegin < $pEnd){
$temp = $array[$pBegin];
$array[$pBegin] = $array[$pEnd];
$array[$pEnd] = $temp;
}
}
return $array;
}
补充
类似题目：
- 将题目改成将数组分成两部分，所有负数在非负数前面；
- 将题目改成将数组分成两部分，能被3整除的在不能被3整除的前面；
为了让代码的扩展性更强，可以将这些判断条件单独写成一个函数接口，而主代码框架保持不变。func()函数即为判断条件的接口。
function reOrderArray($array)
{
if ($array == null || count($array) <= 0) {
return [];
}
$pBegin = 0;
$pEnd = count($array) - 1;
while ($pBegin < $pEnd) {
while ($pBegin < $pEnd && func($array[$pBegin])) {
$pBegin++;
}
while ($pBegin < $pEnd && func($array[$pEnd]))) {
$pEnd--;
}
if($pBegin < $pEnd){
$temp = $array[$pBegin];
$array[$pBegin] = $array[$pEnd];
$array[$pEnd] = $temp;
}
}
return $array;
}
function func($value){
......
}
2. 考虑约束条件
考虑约束条件，需要保持调整后的数组元素，奇数与奇数，偶数与偶数的相对位置不变。
调整前数组的顺序为：[3, 5, 8, 9, 10, 20, 23, 4, 7, 11]
调整后的顺序应该为：[3, 5, 9, 23, 7, 11, 8, 10, 20, 4]
使用双队列的思路，奇数在队列头部插入，偶数采用队列后插入的方法。其中在数组遍历中，每次对数组的头与尾进行判断，奇数的判断需要从数组最后的元素开始，偶数判断从数组头开始。
模拟过程：第一轮：空队列[ ], 11是奇数，则从头部插入[11]; 3不是偶数不插入
第二轮：7是奇数，从头部插入[7, 11]; 5不是偶数不插入
第三轮：4是偶数不插入;8是偶数,从尾部插入[7, 11, 8]
第四轮：23是奇数，从头部插入[23, 7, 11, 8]; 9不是偶数不进行插入
第五轮：20是偶数不插入；10是偶数，从尾部插入[23, 7, 11, 8, 10]
........
- php实现如下：
运行时间：12ms
占用内存：3932k
function reOrderArrayQue($array) {
if ($array == null || count($array) <= 0) {
return [] ;
}
$result = array();
$num = count($array);
for ($i = 0; $i < $num; $i++) {
if ($array[$num - $i - 1] % 2 != 0) {
array_unshift($result, $array[$num - $i - 1]);
}
if ($array[$i] % 2 == 0) {
array_push($result, $array[$i]);
}
}
return $result;
}
- python实现
# -*- coding:utf-8 -*-
from collections import deque
class Solution:
def reOrderArrayI(self, array):
if not array or len(array) <= 0:
return []
res = []
length = len(array)
for i in range(length):
if array[i] % 2 != 0:
res.append(array[i])
for i in range(length):
if array[i] % 2 == 0:
res.append(array[i])
return res
def reOrderArrayII(self, array):
if not array or len(array) <= 0:
return []
res = []
out = []
length = len(array)
for i in range(length):
if array[i] % 2 != 0:
res.append(array[i])
else:
out.append(array[i])
return res + out
'''
双队列方法
运行时间：26ms
占用内存：5628k
'''
def reOrderArrayIII(self, array):
return list(odd)
result = deque()
length = len(array)
for i in range(length):
if array[length - i - 1] % 2 != 0:
result.appendleft(array[length - i - 1])
if array[i] % 2 == 0:
result.append(array[i])
return list(result)
s = Solution()
array = [2,3,8,9,11,23,14,19,20,20,32,11,17,19,33,55]
print s.reOrderArrayI(array)
print s.reOrderArrayII(array)
print s.reOrderArrayIII(array)
知识总结复习
- PHP数组中头部和尾部添加元素的方法(array_unshift,array_push)
参考学习：https://www.jb51.net/article/110822.htm - PHP数组的指针以及文件的指针
参考学习：https://blog.csdn.net/zhyoulun/article/details/53728358
网友评论