调整数组顺序使奇数位于偶数的前面
public class Solution {
public void reOrderArray(int [] array) {
if(array == null || array.length ==0){
return ;
}
int index =0;
for(int i =0;i<array.length;i++){
if(array[i]%2==1){
++index;
}
}
int[] newArray = new int[array.length];
int j =0;
for(int i =0;i < array.length;i++){
if(array[i] %2==1){
newArray[j++] = array[i];
}else{
newArray[index++] = array[i];
}
}
for(int i =0;i<array.length;++i){
array[i] = newArray[i];
}
}
}问题
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路
创建双向队列，遍历数组，奇数前插入，偶数后插入。最后使用assign方法实现不同容器但相容的类型赋值。
因此我们可以维护两个指针，第一个指针初始化时指向数组的第一个数字，它只向后移动：第二个指针初始化时指向数组的最后一个数字， 它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，我们就交换这两个数字。
代码
方法1
public class sortArrayByParity {
public static void main(String[] args) {
int[] A = new int[]{3,8,1,7,2,4};
int[] B = sortArrayByParity(A);
for(int b : B){
System.out.print(b + " ");
}
}
public static int[] sortArrayByParity(int[] A) {
if (A == null) {
return null;
}
if(A.length < 2){
return A;
}
int pHead =0;
int pEnd =A.length-1;
int temp =0;
while (pEnd > pHead){
while (pEnd > pHead && A[pHead] % 2 != 0){
pHead++;
}
while (pEnd > pHead && A[pEnd] % 2 == 0){
pEnd--;
}
temp = A[pHead];
A[pHead] = A[pEnd];
A[pEnd] = temp;
}
return A;
}
}
方法2
偶数&0x1是什么意思？
看见这个0x你肯定知道这就是16进制表示了，而0x1就是最后一位肯定是1。偶数的二进制表示中最后一位肯定是0，如果是奇数那肯定是1，所以一个整数与0x1做按位与运算得到的结果是0或者1就可以判断出这个整数是偶数还是奇数。
public void reorderOddEven1(int []number){
int len = number.length;
if(number == null || len == 0){
return;
}
int begin = 0;
int end = len -1;
while(begin < end){
while((begin < end) && (number[begin] & 0x1) != 0){
++begin;
}
while((begin < end) && (number[end] & 0x1) == 0){
--end;
}
if(begin < end){
int temp = number[begin];
number[begin] = number[end];
number[end] = temp;
}
}
}
自己另外的方法
public class Solution {
public void reOrderArray(int [] array) {
int index =0;
for(int i =0;i<array.length;i++){
if(array[i]%2==1){
++index;
}
}
int m =0;
int[] newarray = new int[array.length];
for(int i =0;i<array.length;i++){
if(array[i]%2==1){
newarray[m++] =array[i];
}else{
newarray[index++]=array[i];
}
}
for(int i =0;i<array.length;i++){
array[i] =newarray[i];
}
}
}拓展
把题目改成把数组中的数按照大小分为两部分，所有的负数都在非负数的前面；
把题目改成把数组中的数按照能不能被3整除分为两部分，所有不能被3整除的数在前面。
上面的两个题目其实它的意图很明显，想让我们把我们上面的函数解耦成两部分：一是判断数字应该在数组前半部分还是后半部分的标准；二是拆分数组的操作。
public boolean isEven(int num){
if((num & 0x1) == 0){
return true;
}else{
return false;
}
}
public boolean isDivideBy3(int num){
if(num % 3 == 0){
return true;
}else{
return false;
}
}
public boolean isNonnegativeNumber(int num){
if(num >= 0){
return true;
}else{
return false;
}
}
public void reorder(int []number){
int len = number.length;
if(number == null || len == 0){
return;
}
int begin = 0;
int end = len -1;
while(begin < end){
while((begin < end) && 方法){
++begin;
}
while((begin < end) && 方法){
--end;
}
if(begin < end){
int temp = number[begin];
number[begin] = number[end];
number[end] = temp;
}
}
}
LeetCode
方法1
public int[] sortArrayByParity(int[] arr) {
// 对于输入的数组为空，或者长度小于2的只接返回
if (arr == null) {
return null;
}
if(arr.length < 2){
return arr;
}
// 从左向右记录偶数的位置
int start = 0;
// 从右向左记录奇数的位置
int end = arr.length - 1;
// 开始调整奇数和偶数的位置
while (start < end) {
// 找偶数
while (start < end && arr[start] % 2 == 0) {
start++;
}
// 找奇数
while (start < end && arr[end] % 2 != 0) {
end--;
}
// 找到后就将奇数和偶数交换位置
// 对于start=end的情况，交换不会产生什么影响
// 所以将if判断省去了
int tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
}
return arr;
}
Integer中方法compare和compareTo的区别
从名字上我们就可以大概才出来他们的区别,compareTo的参数是一个整数,是对象的方法.相对之下compare的参数应该就是两个,是类的方法.
再来看看源码
//compareTo
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
//compare
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}这就很清楚了,compare是静态的,可以通过类名直接调用.Integer.compare(a,b)
compareTo是非静态的,只能通过对象名.compareTo()来调用
compareTo内部其实也是直接调用的compare方法.
对象大于目标参数,返回1
对象小于目标参数,返回-1
对象等于目标参数,返回0
lambda表达式
最简单的例子是 Collections.sort(list, (x, y) -> y - x); 其中
(x, y) -> y - x
是一个lambda表达式，输入两个参数x, y，返回值 x - y。“->”起分隔作用。，Java会自动翻译
方法2
class Solution {
public int[] sortArrayByParity(int[] A) {
Integer[] B = new Integer[A.length];
for (int t = 0; t < A.length; ++t)
B[t] = A[t];
Arrays.sort(B, (a, b) -> Integer.compare(a%2, b%2));
for (int t = 0; t < A.length; ++t)
A[t] = B[t];
return A;
}
}
京公网安备 11010502036488号