今天题目有两道,分为一和二 题目链接:调整数组顺序使奇数位于偶数前面(一) 题目链接:调整数组顺序使奇数位于偶数前面(二)
难度:中等
输入一个长度为 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的位置。然后再找下一个偶数,重复这一过程,最终就可以将奇数都放到偶数的前面,并且保证了相对位置的不变。
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<n && j<n){
//找到第一个偶数
while(i<n && array[i]%2!=0){
i++;
}
//找到第一个偶数后的第一个奇数
j= i+1;
while(j<n && array[j]%2==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)
这道题不需要要求相对位置不变,因此我们可以采用位置交换的方法,只要奇数全部换到前面就可以了。
利用左右双指针分别从数组首尾出发向中间走,交换其中的偶数在前奇数在后的情况。
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;
}
}