【剑指offer】-调整数组顺序使奇数位于偶数前面-13/67

1. 题目描述

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

2. 题目分析

  1. 第一个做法:以时间换空间,复杂度O(n²)

    1
    2
    3
    1. 遍历数组array,利用num来记录当前奇数的个数
    2. 当遍历到奇数时,利用交换的思想,将此时的奇数交换至array[num]的位置
    3. 最终,得到最后的结果
  2. 第二个做法:以空间换时间,复杂度O(n)

    1
    2
    3
    1. 开辟一个新的数组a,定义num1(代表array数组中奇数的个数),num2(代表a数组中偶数的个数)
    2. 遍历数组array。如果是奇数,将其array[num1++],如果是偶数,将其a[num2++]
    3. 最后,将a数组中的偶数转移到array数组中

3. 题目代码

  1. 第一个做法:以时间换空间,复杂度O(n²)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public void reOrderArray(int[] array) {
    int num = 0;
    int j = 0;
    int temp = 0;
    for (int i = 0; i < array.length; i++) {
    if (array[i] % 2 == 1) {
    j = i;
    while (j > num) {
    temp = array[j];
    array[j] = array[j - 1];
    array[j - 1] = temp;
    j--;
    }
    num++;
    }
    }
    }
  2. 第二个做法:以空间换时间,复杂度O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public void reOrderArray(int [] array) {
    int[] a = new int[100];
    int num1 = 0;
    int num2 = 0;
    for(int i = 0; i < array.length; i++){
    if(array[i] % 2 == 0){
    a[num1++] = array[i];
    }else{
    array[num2++] = array[i];
    }
    }
    for(int i = 0; i < num1; i++){
    array[num2++] = a[i];
    }
    }
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信