JZ81调整数组顺序使奇数位于偶数前面(二)
描述
输入一个长度为 n 整数数组,数组里面可能含有相同的元素,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前面部分,所有的偶数位于数组的后面部分,对奇数和奇数,偶数和偶数之间的相对位置不做要求,但是时间复杂度和空间复杂度必须如下要求。
方法1
思路:
既然要把所有的奇数放在数组前面,所有的偶数放在数组后面,那可以统计奇数在原数组中出现了多少次,这样就可以找到二者的分界线。有了分界线以后,前面就是奇数,后面就是偶数,可以利用两个指针分别指向二者的开头,遇到一个元素就添加到相应位置,然后指针移动。(该方法保证了相对位置不变)
代码
public int[] reOrderArrayTwo (int[] array) {
// write code here
if (array.length <= 0) return new int[0];
int[] result = new int[array.length];
int y = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] % 2 == 1) y++;
}
int x = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] % 2 == 1) {
result[x] = array[i];
x++;
}
if (array[i] % 2 == 0) {
result[y] = array[i];
y++;
}
}
return result;
}
方法2
思路
这道题不需要要求相对位置不变,因此我们可以采用位置交换的方法,只要奇数全部换到前面就可以了。利用左右双指针分别从数组首尾出发向中间走,交换其中的偶数在前奇数在后的情况。(该方法不能保证相对位置不变)
代码
package esay.JZ81调整数组顺序使奇数位于偶数前面2;
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param array int整型一维数组
* @return int整型一维数组
*/
//方法1
/*public int[] reOrderArrayTwo (int[] array) {
// write code here
if (array.length <= 0) return new int[0];
int[] result = new int[array.length];
int y = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] % 2 == 1) y++;
}
int x = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] % 2 == 1) {
result[x] = array[i];
x++;
}
if (array[i] % 2 == 0) {
result[y] = array[i];
y++;
}
}
return result;
}*/
//方法2
public int[] reOrderArrayTwo(int[] array) {
// write code here
int i = 0;
int j = array.length - 1;
while (i < j) {
//左边奇数,右边偶数
if (array[i] % 2 == 1 && array[j] % 2 == 0) {
i++;
j--;
}
//左右全是奇数
else if (array[i] % 2 == 1 && array[j] % 2 == 1) {
i++;
}
//左边偶数,右边奇数
else if (array[i] % 2 == 0 && array[j] % 2 == 1) {
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
//左右全是偶数
else {
j--;
}
}
return array;
}
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 4};
System.out.println(Arrays.toString(new Solution().reOrderArrayTwo(arr)));
}
}
当前文章:每日算法之调整数组顺序使奇数位于偶数前面(二)
文章来源:
http://njwzjz.com/article/dsdihpj.html