剑指offer

剑指offer(十三)调整数组顺序使奇数位于偶数前面

2020-04-01  本文已影响0人  向前的zz

点击进入 牛客网题库:调整数组顺序使奇数位于偶数前面

题目描述

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

上来我就撸了一个,借助List来进行的,不过这个肯定不是面试官想要的

方法一:

  /**
     * 算法 时间复杂度O(n) 空间复杂度 O(n) 
     * @param array
     */
 public void reOrderArray(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        final ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 != 0) {
                list.add(array[i]);
            }
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                list.add(array[i]);
            }
        }

        for (int i = 0; i < array.length; i++) {
            array[i] = list.get(i);
        }
    }

方法二:

j 遇到奇数就进行交换,然后把所有的偶数往后调整,然后,再把奇数赋值到原来的偶数上

一个比较糟糕的图解(第一次画图,比较瑕疵,凑合着看把[😂])


剑指offer topic13图解.png

代码:

  /**
     * 算法 时间复杂度O(n^2) 空间复杂度 O(1)
     *
     * @param array
     */
    public void reOrderArray(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        int m = 0;
        for (int i = 0; i < array.length; i++) {
            //判断奇数类型 符合条件
            if (array[i] % 2 != 0) {
                //把这个奇数保存起来
                int tmp = array[i];
                int j = i;
                while (j > m) {
                    //一顿交换,把偶数往前走一步
                    array[j] = array[j - 1];
                    j--;
                }
                //奇数占用原来偶数的位置,偶数的位置向前移动了一步
                array[j] = tmp;
                //m指向偶数位置,等待下次的交换
                m = j + 1;
            }

        }
    }
上一篇 下一篇

猜你喜欢

热点阅读