Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1516
Question Name: Reorder Array
Question Description: Give an array of integers, reorder it so that, all odd numbers are before all even numbers. The order among odd numbers is kept. And so are the even numbers.
Input: first line is an integer N, saying the size of the test array. The second line contains N integers, being the test case.
Output: the reordered array.
1 2 3 4 5 | Input: 5 1 2 3 4 5 Output: 1 3 5 2 4 |
Follow up: if the order among odd numbers and among even numbers is not kept. Could you do it in O(1) space and O(N) time?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | /** * Filename : ReorderArray.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-08-07 * JDK used : 1.7 * Change log: None */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.ArrayList; import java.util.List; public class ReorderArray { /** * Reorder the array to make all odd numbers before all even number, while * keeping the order among odd numbers and among even numbers. * @param array : the integer array to re-order. */ public void reorderArray(int[] array) { List<Integer> odd = new ArrayList<Integer>(); // Store all odd numbers List<Integer> even = new ArrayList<Integer>(); // Store all even numbers // Store all the odd and even numbers separately, while keeping the order // among odd numbers and among even numbers respectively. for (int item : array) { if ((item & 1) == 1) odd.add(item); else even.add(item); } // Write back the odd numbers firstly, and then the even numbers. int index = -1; for (int item : odd) array[++index] = item; for (int item : even) array[++index] = item; return; } /** * Reorder the array to make all odd numbers before all even number. * The solution is similar with quick sort algorithm. * @param array : the integer array to re-order. */ public void reorderArrayII(int[] array) { // The position to write the next odd number and even number. int nextToWriteOdd = 0; int nextToWriteEven = array.length - 1; int i = 0; int temp; while(nextToWriteOdd < nextToWriteEven) { if ((array[i] & 1) == 1) { // Odd number if (nextToWriteOdd == i) { ++nextToWriteOdd; ++i; } else { temp = array[i]; array[i] = array[nextToWriteOdd]; array[nextToWriteOdd] = temp; ++nextToWriteOdd; } } else { // Even number temp = array[i]; array[i] = array[nextToWriteEven]; array[nextToWriteEven] = temp; --nextToWriteEven; } } return; } /** * Stub for testing * @param args * @throws IOException */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int[] array = null; int size = 0; // Get the test size. if(st.nextToken() != StreamTokenizer.TT_EOF) { size = (int) st.nval; } else { System.out.println("Invalid input."); return; } // Get the test array. array = new int[size]; while (size > 0 && st.nextToken() != StreamTokenizer.TT_EOF) { array[array.length - size] = (int) st.nval; size -= 1; } // Reorder the array ReorderArray reorder = new ReorderArray(); reorder.reorderArray(array); // Output the array after reordering. System.out.print(array[0]); for (int i = 1; i < array.length; ++i) { System.out.print(" "); System.out.print(array[i]); } return; } } |