输入一个整数数组,实现一个函数来调整该数组中数字的顺序, 使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分, 并保证奇数和奇数,偶数和偶数之间的相对位置不变。

package array;

public class 调整数组顺序使奇数位于偶数前面 {
    /**
     * 自想1:
     * 另外用一个数组
     * 时间复杂度O(n),空间复杂度O(n)
     */
    public void reOrderArray1(int[] array) {
        if (array == null || array.length <= 0) {
            return;
        }
        int[] res = new int[array.length];
        int i = 0;
        for (int num : array) {
            if (num % 2 == 1) {
                res[i++] = num;
            }
        }
        for (int num : array) {
            if (num % 2 == 0) {
                res[i++] = num;
            }
        }
        for (int j = 0; j < array.length; j++) {
            array[j] = res[j];
        }
    }

    /**
     * 自想2:插入排序的思想
     * 从1-最后,从这个数看前面的数,当前数是奇数,前一个数不是奇数就前移,相邻交换
     * 时间复杂度O(n²),空间复杂度O(1)
     */
    public void reOrderArray2(int[] array) {
        if (array == null || array.length <= 0) {
            return;
        }
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] % 2 == 1 && array[j - 1] % 2 == 0) {
                    swap(array, j, j - 1);
                }
            }
        }
    }

    public static void swap(int[] array, int i, int j) {
        if (i == j) {
            return;
        }
        array[i] = array[i] ^ array[j];
        array[j] = array[i] ^ array[j];
        array[i] = array[i] ^ array[j];
    }


    /**
     * 讨论区:
     * 要想保证原有次序,则只能顺次移动或相邻交换。
     * 这里采用顺次移动
     * i存偶数的下标,j存i之后的奇数的下标
     * i从左向右遍历,找到第一个偶数。
     * j从i+1开始向后找,直到找到第一个奇数。
     * 将[i,...,j-1]的元素整体后移一位,最后将找到的奇数放入i位置,然后i++。
     * 终止条件:j向后遍历没有再找到奇数。
     * 时间复杂度O(n²),空间复杂度O(1)
     */
    public static void reOrderArray3(int[] array) {
        if (array == null || array.length <= 0) {
            return;
        }
        // array[i]是第一个偶数
        int i = 0;
        for (; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                break;
            }
        }
        // array[j]是array[i]后面的第一个奇数
        int j = i + 1;
        while (j < array.length) {
            for (; j < array.length; j++) {
                if (array[j] % 2 == 1) {
                    break;
                }
            }
            // 如果array[i]后面没有奇数,证明奇数全部在偶数的前面
            if (j >= array.length) {
                return;
            }
            // 记下即将被覆盖的最后一个值
            int odd = array[j];
            // 向后移必须从后往前移动,不然前面的向后移会覆盖后面的值
            for (int k = j - 1; k >= i; k--) {
                array[k + 1] = array[k];
            }
            array[i++] = odd;
            j++;
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 2, 4, 6};
        reOrderArray2(array);
    }
}

results matching ""

    No results matching ""