调整数组顺序使奇数位于偶数前面(一)
难度：中等
描述
输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
数据范围
数据范围：0≤n≤5000，数组中每个数的值 0≤val≤10000
要求：时间复杂度 O(n)，空间复杂度 O(n)
进阶：时间复杂度 O(n2)，空间复杂度 O(1)
举例
解题思路
首先，如果不考虑奇数和奇数，偶数和偶数的相对位置，那么我们有一种双指针解法来求解，类似于快排，维护两个指针，第一个指针指向数组的第一个数字，第二个指针指向数组的最后一个数字。第一个指针向后移，第二个指针向前移，如果第一个指针指向偶数，第二个指针指向的是奇数，则交换着两个数字，接着继续移动直到两指针相遇。
上面的方法看似不错，但是对本题不适用，因为本题有相对位置不变的要求，直接交换会导致相对位置改变。因此，我们采用下面的思路来解决本题。
本题解法：对数组进行遍历，设置两个指针even和odd，even指向当前第一个偶数，odd从这个偶数之后开始查找，找到第一个奇数，此时为了相对位置不变，不能直接交换even和odd，而是将从even到odd-1的元素都依次向后移一个位置，将odd指向的那个奇数放到even的位置。然后再找下一个偶数，重复这一过程，最终就可以将奇数都放到偶数的前面，并且保证了相对位置的不变。
编程实现（java）
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型一维数组 * @return int整型一维数组 */ public int[] reOrderArray (int[] array) { // write code here int i = 0,j = 0; int n = array.length; while(i //找到第一个偶数 while(i2!=0){ i++; } //找到第一个偶数后的第一个奇数 j= i+1; while(j2==0){ j++; } //注意判断，防止溢出 if(j>=n) break; //把偶数与奇数之间的所有偶数往后移动，奇数与该偶数位置的元素对调 //先把偶数后第一个奇数保存下来，因为接下来的移动过程中会替换掉该奇数 int t = array[j]; for(int k = j-1;k>= i;k--){ array[k+1] = array[k]; } //把奇数填到第一个偶数往后移动，所腾出来的位置 array[i] = t; i++; } return array; } }
结果
调整数组顺序使奇数位于偶数前面(二)
难度：简单
描述
输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。
数据范围
数据范围：0≤n≤50000，数组中每个数的值 0≤val≤10000
要求：时间复杂度 O(n)，空间复杂度 O(1)
举例
解题思路
这道题不需要要求相对位置不变，因此我们可以采用位置交换的方法，只要奇数全部换到前面就可以了。
利用左右双指针分别从数组首尾出发向中间走，交换其中的偶数在前奇数在后的情况。
编程实现（java）
import java.util.*; public class Solution { public int[] reOrderArrayTwo (int[] array) { //双指针 int i = 0; int j = array.length - 1; //向中间聚合 while(i < j){ //左右都是奇数，左移右不动 if(array[i] % 2 == 1 && array[j] % 2 == 1) i++; //左奇数右偶数，左右都向中间缩 else if(array[i] % 2 == 1 && array[j] % 2 == 0){ i++; j--; } //左偶右奇数 else if(array[i] % 2 == 0 && array[j] % 2 == 1){ //交换 int temp = array[i]; array[i] = array[j]; array[j] = temp; } //左右都是偶数，只移动右指针 else j--; } return array; } }
结果
