This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

The title

21. Reorder the array so that the odd number precedes the even number

describe

Take an array of integers and implement a function to adjust the order of the numbers in the array so that all odd numbers are in the first half of the array and all even numbers are in the second half.

Example:

Input: nums = [1,2,3,4]

Output:,3,2,4 [1]

[3,1,2,4] is also one of the correct answers.

Tip:

  1. 1 <= nums.length <= 50000
  2. 1 <= nums[i] <= 10000

Implementation method

Method 1

Train of thought

Then define an array. Add the elements of the list storing odd and even numbers to the array and return them. The main operation is traversal, so the final complexity is O(n)O(n)O(n).

implementation

public int[] exchange(int[] nums) {
    // Store the final result
    int[] result = new int[nums.length];
    // Store even numbers
    ArrayList<Integer> listEven = new ArrayList<>();
    // store odd numbers
    ArrayList<Integer> listOdd = new ArrayList<>();

    // Iterate over the number group, storing the elements separately in the list
    for(int num : nums){
        if(num % 2= =0){
            listEven.add(num);
        }else{ listOdd.add(num); }}// Store odd and even numbers into the final result array, respectively
    for(int i  = 0; i < listOdd.size(); i++){ result[i] = listOdd.get(i); }for(int i  = listOdd.size(); i < listEven.size() + listOdd.size(); i++){
        result[i] = listEven.get(i - listOdd.size());
    }

    return result;
}
Copy the code

Method 2

Train of thought

Double pointer, two Pointers are used to obtain the final result, the fast pointer is used to traverse the number group, and the slow pointer is used to point to the number of elements stored in the final result array, the main operation is twice traversal operation, so the time complexity is 2O(n)=O(n)2O(n) =O(n)2O(n) =O(n);

implementation

public int[] exchange(int[] nums) {
    // Store the final result
    int[] result = new int[nums.length];

    int index = 0;
    // Add the odd number to the final array
    for(int num : nums){
        if(num % 2! =0){ result[index++] = num; }}// Add the even number to the final result array
    for(int num : nums){
        if(num % 2= =0){ result[index++] = num; }}return result;
}
Copy the code