题解 | #调整数组顺序使奇数位于偶数前面#
调整数组顺序使奇数位于偶数前面
http://www.nowcoder.com/practice/ef1f53ef31ca408cada5093c8780f44b
算法思想一：使用辅助数组
解题思路：
创建两个全新的数组，遍历原数组将其奇数和偶数分别存放在两个数组中，最后将两个数组合并（奇数组放在偶数组前面）
图解：
数组：【1，2，3，4】
| 步骤 | 原数组 | 奇数组 | 偶数组 |
| 1 | 【1，2，3，4】 | 【1】 | 【】 |
| 2 | 【1，2，3，4】 | 【1】 | 【2】 |
| 3 | 【1，2，3，4】 | 【1，3】 | 【2】 |
| 4 | 【1，2，3，4】 | 【1，3】 | 【2，4】 |
| 最后合并奇数组、偶数组为【1，3，2，4】 | |||
代码展示：
class Solution: def reOrderArray(self , array ): # write code here odd = [] even = [] for i in range(len(array)): if array[i] % 2 ==0: # 偶数存储 even.append(array[i]) else: # 奇数存储 odd.append(array[i]) array.clear() # 组合两个数组 array = odd+even return array复杂度分析：
时间复杂度O(N)：N表示原数组的长度，遍历原数组
空间复杂度O(N)：需要N个存储空间
算法思想二：在原数组上修改
解题思路：
初始化：记录变量 i 表示将奇数放好的下一个未知，最开始 i = 0表示没有一个奇数，j 表示数组的下标，对数组进行遍历
若遇到偶数则 j++
如果遇到奇数，将 j 位置的奇数插入到 i 的位置，然后将 i 后移一位，会涉及【i, j - 1】整体移动，直到整个数组遍历结束
图解：
代码展示：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArray (int[] array) {
// write code here
int i = 0;
for (int j=0; j < array.length; ++j) {
// 遇到奇数时
if (array[j] % 2 == 1) {
// 先将 array[j] 赋值
int tmp = array[j];
// 将 【i, j-1】数组后移动
for (int k=j-1; k>=i; --k) {
array[k+1] = array[k];
}
// 将array[j]插入到 i++ 的位置
array[i++] = tmp;
}
}
return array;
}
} 复杂度分析：
时间复杂度O(N^2)：最差的情况（一半偶数在前，一半奇数在后），每次都需要移动 n/2 个元素，则一共需要 n^2/4
空间复杂度O(1)：不需要额外空间
投递柠檬微趣等公司10个岗位 >
查看6道真题和解析