剑指offer_数组---调整数组顺序使奇数位于偶数前面

简介: 剑指offer_数组---调整数组顺序使奇数位于偶数前面

##题目描述

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

##解题思路

1,暴力遍历法,取出所有奇数放到一个数组里,取出所有偶数放到一个数组里,然后把所有奇数和偶数先后放入原数组

2,插入法,时间复杂度也是o(n^2)但是不需要开辟额外空间

##代码实现

package 数组;
/**
 * 
 * 输入一个整数数组,实现一个函数来调整该数组中数字的顺序 使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分
 * 并保证奇数和奇数,偶数和偶数之间的相对位置不变。
 */
public class ReOrderArray {
  public static void main(String[] args) {
    int[] array = { 1, 2, 3, 4, 5 };
    new ReOrderArray().reOrderArray(array);
  }
  // ===============================================================暴力遍历法空间占用o(n),时间占用o(n^2)
  public void reOrderArray(int[] array) {
    if (array == null || array.length < 1) {
      return;
    }
    int size = array.length;
    int sinlen = 0;
    for (int i = 0; i < size; i++) {
      if (array[i] % 2 == 1) {
        sinlen++;
      }
    }
    int doulen = size - sinlen;
    // System.out.println(doulen);
    int[] sinArray = new int[sinlen];
    int[] douArray = new int[doulen];
    int j = 0;
    int k = 0;
    for (int i = 0; i < size; i++) {
      if (array[i] % 2 == 0) {
        douArray[j++] = array[i];
      }
      if (array[i] % 2 == 1) {
        sinArray[k++] = array[i];
      }
    }
    for (int i = 0; i < sinlen; i++) {
      array[i] = sinArray[i];
      System.out.print(sinArray[i]);
    }
    System.out.println();
    for (int i = 0; i < doulen; i++) {
      array[sinlen + i] = douArray[i];
      System.out.print(douArray[i]);
    }
    System.out.println();
    for (int i = 0; i < size; i++) {
      System.out.print(array[i]);
    }
  }
  // ==============================================================优化解法
  /**
   * 1.要想保证原有次序,则只能顺次移动或相邻交换。 2.i从左向右遍历,找到第一个偶数。 3.j从i+1开始向后找,直到找到第一个奇数。
   * 4.将[i,...,j-1]的元素整体后移一位,最后将找到的奇数放入i位置,然后i++。 5.終止條件:j向後遍歷查找失敗。
   */
  public void reOrderArraySuper(int[] array) {
    if (array == null || array.length < 1) {
      return;
    }
    int i = 0;
    int j = 0;
    while (i < array.length) {
      while (i < array.length && isSingle(array[i]))
        i++;                   
      j = i+1;              //第一个偶数的位置
      while(j<array.length&&!isSingle(array[j]))
        j++;             //j从i+1开始向后找,直到找到第一个奇数。
      if(j<array.length){
        int temp = array[j];  //当前j的位置在i之后的第一个奇数
        for (int k = j-1; k >=i; k--) {
          array[k+1] = array[k];            //向后移动位置
        }
        array[i] = temp;
        i++;
      }else{
        break;
      }   
    }
  }
  // 用于判断是否为奇数的函数
  public boolean isSingle(int num) {
    if (num % 2 == 1)
      return true;
    else
      return false;
  }
}


相关文章
【剑指offer】-调整数组顺序使奇数位于偶数前面-13/67
【剑指offer】-调整数组顺序使奇数位于偶数前面-13/67
调整数组使奇数全部都位于偶数前面
调整数组使奇数全部都位于偶数前面
67 0
|
10月前
【调整奇数偶数顺序】调整数组使奇数全部都位于偶数前面习题集讲解
【调整奇数偶数顺序】调整数组使奇数全部都位于偶数前面习题集讲解
81 1
|
10月前
|
Java
每日一题《剑指offer》数组篇之调整数组顺序使奇数位于偶数前面
每日一题《剑指offer》数组篇之调整数组顺序使奇数位于偶数前面
77 0
每日一题《剑指offer》数组篇之调整数组顺序使奇数位于偶数前面
剑指Offer - 面试题21:调整数组顺序使奇数位于偶数前面
剑指Offer - 面试题21:调整数组顺序使奇数位于偶数前面
65 0
剑指offer 20. 调整数组顺序使奇数位于偶数前面
剑指offer 20. 调整数组顺序使奇数位于偶数前面
64 0
|
算法 前端开发
【脚趾 Offer 21 】调整数组顺序使奇数位于偶数前面
【脚趾 Offer 21 】调整数组顺序使奇数位于偶数前面
136 0
AcWing 32. 调整数组顺序使奇数位于偶数前面
AcWing 32. 调整数组顺序使奇数位于偶数前面
98 0
AcWing 32. 调整数组顺序使奇数位于偶数前面
|
算法
【刷算法】调整数组顺序使奇数位于偶数
【刷算法】调整数组顺序使奇数位于偶数
LeetcCode——剑指Offer21【调整数组使其奇数位于偶数前面】
LeetcCode——剑指Offer21【调整数组使其奇数位于偶数前面】
LeetcCode——剑指Offer21【调整数组使其奇数位于偶数前面】