题解 | #调整数组顺序使奇数位于偶数前面#

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
示例1
输入：
[1,2,3,4]
返回值：
[1,3,2,4]

示例2
输入：
[2,4,6,5,7]
返回值：
[5,7,2,4,6]

题目思想：

所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分
保证原有的次序，则只能顺序移动或者相邻交换

方法一：暴力法

遍历数组找到奇数的位置，然后使原来的数组整体向后移

代码如下：

 //使用插入排序的思想
    public int[] reOrderArray (int[] arr){

        if(arr==null||arr.length==0){
           return arr; 
        }

        int j=0;//记录已经是奇数的位置
        int temp = 0;
        for(int i =0;i<arr.length;i++){
            temp = arr[i];
            //若是偶数则跳过进行下一次循环
            if(arr[i]%2==0){
                continue;
            }else{
                int k =i;
                while(k>j){
                    arr[k] = arr[k-1];//这区间整体向后移动一位
                    k--;
                }
                arr[k] = temp;
                j++;
            }
        }
        return arr;
    }

时间复杂度：O(n^2)，因为找到每个奇数，都需要移动数组里的元素，所以他的时间复杂程度比较复杂

方法二：优化解

遍历数组，统计奇数和偶数的个数统计出来并临时存放，在新数组中先放奇数再放偶数

代码如下：

 public int[] reOrderArray (int[] arr) {

        int oddCount = 0, evenCount = 0;
        int[] newArr = new int[arr.length];

        // 统计原数组中奇数的个数
        for (int i = 0; i < arr.length; i++) {
            if((arr[i] & 1) == 1){
                oddCount++;
            }
        }
        //统计原数组中偶数的个数
        for (int i = 0; i < arr.length; i++) {
            if((arr[i] & 1) == 1){
                // 在新数组中，先放奇数，从头开始放
                newArr[evenCount++] = arr[i];
            }else{
                // 偶数从奇数总个数后开始放
                newArr[oddCount++] = arr[i];
            }
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = newArr[i];
        }
        return arr;
    }

时间复杂度：O(n)，其中n是数组中元素个数