15.调整数组顺序使奇数位于偶数前面

题目描述

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

解题思路

运用插入思想

  1. 要想让相对位置不变,则需要相邻位置交换
  2. 引入标志位k 表示前半部分最后一个奇数位置
  3. 寻找到下一个奇数时,将标志位 k 之后到当前奇数位置上的数按照顺序从后向前相邻移动奇数到k位置

代码实现

java 代码

public void reOrderArray(int[] array) {
    int k = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i] % 2 != 0) {
            for (int j = i; j > k; j--) {
                int temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
            }
            k++;
        }
    }
}

public static void main(String[] args){
    int[] arr = {4,1, 3, 2, 5, 7, 4, 6, 9, 8, 3};
    reOrderArray(arr);
    System.out.println(Arrays.toString(arr));
}

Kotlin 代码

/**
 * 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
 * 运用插入思想
 * 1. 要想让相对位置不变,则需要相邻位置交换
 * 2. 引入标志位k 表示前半部分最后一个奇数位置
 * 3. 寻找到下一个奇数时,将标志位 k 之后到当前奇数位置上的数按照顺序从后向前相邻移动奇数到k位置
 * @param array
 */
fun reOrderArray(array: IntArray) {
    var k = 0
    for (i in array.indices) {
        if (array[i] % 2 != 0) {
            for (j in i downTo k + 1) {
                val temp = array[j - 1]
                array[j - 1] = array[j]
                array[j] = temp
            }
            k++
        }
    }
}


/**
 * 入口函数
 */
fun main(args: Array<String>) {
    val arr = intArrayOf(4, 1, 3, 2, 5, 7, 4, 6, 9, 8, 3)
    reOrderArray(arr)
    println(arr.contentToString())
}

引用声明

该题目引用自
牛客网