github地址

题目描述

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

最暴力的解法: 新写一个数组,遍历一遍原数组将奇数放入头部,偶数放入尾部。O(n),O(n)


    /**
     * 使用两个数组,
     * 从前遍历旧数组找到所有的奇数并放入新数组,
     * 从前遍历旧数组找到所有的奇数并放入新数组。
     * 空间O(n),时间O(n)
     */
    public void reOrderArray(int[] array) {
//        solutionBySort(array);
        // 双数组
        // copy原数组顺序
        int[] copy = new int[array.length];
        System.arraycopy(array, 0, copy, 0, array.length);
        // 从前到后遍历找到所有奇数,放入结果数组中
        int j = 0;
        for (int i = 0; i < array.length; i++) {
            if (copy[i] % 2 == 1) {
                array[j++] = copy[i];
            }
        }
        // 从前到后遍历找到所有偶数,放入结果数组中
        for (int i = 0; i < array.length; i++) {
            if (copy[i] % 2 == 0) {
                array[j++] = copy[i];
            }
        }
        // 上述两步可以合并为一步,但是我懒。
    }

其实这道题对java使用者来说简单,因为Java中的Arrays.sort()是基于归并排序的,(稳定的排序,但是需要O(n)的空间),而C++中的是sort()和qsort()是不稳定的(O(1)空间),所以Java这题可以直接实现Comparator接口,当然空间O(1),时间O(n*log n).


    /**
     * 使用Java自带的比较器功能
     * 时间O(n*log(n))-->双轴排序,空间O(1)
     */
    private void solutionBySort(int[] array) {
        Integer[] a = new Integer[array.length];
        for (int i = 0; i < array.length; i++) {
            a[i] = array[i];
        }
        Arrays.sort(a, new Comp());
        for (int i = 0; i < array.length; i++) {
            array[i] = a[i];
        }
    }

/**
 * 自定义比较器,奇数比偶数小。
 */
class Comp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        if (o1 % 2 == o2 % 2) {
            return 0;
        } else if (o1 % 2 == 0 && o2 % 2 == 1) {
            return 1;
        } else {
            return -1;
        }
    }
}

如果不想使用任何辅助空间,可以使用插入排序,时间复杂度:O(n^2).

 /**
     * 通过插入排序实现,不使用额外内存空间,但是时间效率较低:O(n^2)
     *
     * @param arr
     */
    private void solutionByInsertSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 == 0) {
                // 偶数不动
            } else {
                // 奇数向前走,走到前面的元素不是偶数未知
                for (int j = i; j >= 1 && arr[j - 1] % 2 == 0; j--) {
                    swap(arr, j, j - 1);
                }
            }

        }
        System.out.println(Arrays.toString(arr));
    }

 

 

 

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐