输入一个无序整数数组,调整数组中数字的顺序, 所有偶数位于数组的前半部分,使得所有奇数位于数组的后半部分。
要求时间复杂度为O(n)。
给定无序数组。
长度不超过1000000。
所有偶数位于数组的前半部分,所有奇数位于数组的后半部分。
如果有多个答案可以输出任意一个正确答案。
2 4 5 7 8 1
2 4 8 7 5 1
请自觉使用O(n)的算法。
import java.util.Scanner; public class Test01 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String line = scanner.nextLine(); String[] stringArray = line.split(" "); int[] arr = new int[stringArray.length]; for(int i = 0;i < stringArray.length;i++) { arr[i] = Integer.parseInt(stringArray[i]); } int low = 0; int high = arr.length-1; while(low < high) { if(arr[low] % 2 == 0) { low++; } if(arr[high] % 2 != 0) { high--; } if(low < high) { int temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; } } for(int i = 0;i <arr.length;i++) { System.out.print(arr[i]); System.out.print(" "); } } }
/*
双指针,从头和从尾开始排除符合前面偶数,后面基数的,遇到不符合是就交换,结束条件
*/
import java.util.*;
public class Main {
private static void swap(int [] array){
if (array == null || array.length == 0)
return;
int low = 0, high = array.length - 1;
while(low < high){
if (array[low] % 2 == 0){
low ++;
}
if (array[high] % 2 == 1){
high --;
continue;
}
int temp = array[low];
array[low] = array[high];
array[high] = temp;
}
}
//输入输出
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
//切割
String [] Astr = str.split(" ");
//数组
int n = Astr.length;
int[] array = new int[n];
for(int i = 0; i < n; i ++){
array[i] = Integer.parseInt(Astr[i]);
}
//调用主函数Solution
swap(array);
for (int i = 0; i < array.length; i++){
System.out.print(array[i] + " ");
}
}
} import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc= new Scanner(System.in); String str=sc.nextLine(); String[] s=str.split(" "); method(s); for(int x=0;x<s.length;x++){ System.out.print(s[x]+" "); } } private static void method(String[] s) { int len =s.length; if(len<=1){ return; } int i=0; while(i<len){ int j=i+1; if(Integer.parseInt(s[i])%2==1){ while(Integer.parseInt(s[j])%2==1){ if(j==len-1){ return; } j++; } int count=j-i; int temp=0; temp=Integer.parseInt(s[i]); s[i]=s[j]; while(count>1){ s[i+count]=s[i+count-1]; count--; } s[i+1]=String.valueOf(temp); } i++; } } }
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str=sc.nextLine();
String[] sArr = str.split(" ");
int arr[] = new int[sArr.length];
for(int i = 0; i < sArr.length; i++) {
arr[i] = Integer.parseInt(sArr[i]);
}
int n=arr.length;
int low = 0;
int high=n-1;
while(low<high){
if(arr[low]%2==0){
low++;
}
if(arr[high]%2==1){
high--;
continue;
}
int temp=arr[low];
arr[low]=arr[high];
arr[high]=temp;
}
for(int i=0;i<n;i++){
System.out.print(arr[i]+" ");
}
}
}