Sword finger offer 21 adjusts the array order so that odd numbers precede even numbers LeetCode 905

Enter an integer array, and implement a function to adjust the order of 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 of the array.

Example:

Input: num = [1,2,3,4]
Output: [1,3,2,4]
Note: [3,1,2,4] is also one of the correct answers.

Tips:

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

Solution 1: using double pointers

Create an array res with the same length as nums and traverse nums. When the current element is odd, put it from front to back, left + +. When the current element is even, put it from back to front, right --.

class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0) return nums;
        int[] res = new int[nums.length];
        int left = 0;
        int right = nums.length-1;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] % 2 != 0){//Odd numbers from front to back
                res[left++] = nums[i];
            }else{//Even numbers from back to front
                res[right--] = nums[i];
            }
        }
        return res;

    }
}

Solution 2: quick sorting idea

The essence is still to use the idea of double pointers, but there is no need for additional space. Let left point to the leftmost side of the array, right point to the rightmost side of the array, and left keep moving to the right until the pointing element is not odd, and right moves to the left until the pointing element is not even, and then exchange the elements pointed to by the two pointers. Before the two pointers meet, the left pointer is always in front of the right pointer, Then start the next cycle. The condition for exiting the cycle is left > right. In fact, it is not difficult to find that this is actually a cycle in the idea of quick sorting.

class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0) return nums;
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            //Here left < num The judgment of length cannot be omitted. If all numbers are odd [1,3,5], if this condition is not written, the array subscript in left will be out of bounds. The same is true for right
            while(left < nums.length && nums[left] % 2 != 0) left++;
            while(right >= 0 && nums[right] % 2 == 0) right--;
            /*The if judgment here cannot be omitted, because at the junction, such as [1,3,2,4]
            After the above two while, left points to 2 and right points to 3. There is no need to exchange*/
            if(left < right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return nums;
    }
}

Extended questions: it is necessary to ensure that the relative positions between odd numbers and odd numbers, even numbers and even numbers remain unchanged

It is necessary to ensure that the relative positions between odd numbers and odd numbers, even numbers and even numbers remain unchanged, which is different from the above. The above solution cannot ensure that the relative positions remain unchanged. For example, for [1,2,3,4,5], we should get [1,3,5,2,4] after adjustment, not the result of the change of relative position of [1,3,5,4,2].

Problem solving ideas:

Use the idea of solution 1 above, but first traverse the array to calculate the odd count in the array. Then, instead of putting the even number forward from the last, put it back from the position of count, because the array subscript starts from 0, and count odd numbers will occupy the position of the first count-1 subscript.

Java code

class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0) return nums;
        int count = 0；
        for(int num : nums){//Find the number of odd numbers in the array
            if(num % 2 != 0){
                count++;
            }
        }
        
        int[] res = new int[nums.length];
        int left = 0;
        int right = count;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] % 2 != 0){//Odd numbers from front to back
                res[left++] = nums[i];
            }else{//Even numbers are put back from count
                res[right++] = nums[i];
            }
        }
        return res;

    }
}