输入一个无序整数数组,调整数组中数字的顺序, 所有偶数位于数组的前半部分,使得所有奇数位于数组的后半部分。
要求时间复杂度为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]+" "); } } }