【剑指Offer】13、调整数组顺序使奇数位于偶数前面

一、题目描述

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

二、代码

版本1：My

思路：从前往后遍历数组，判断每个数的奇偶并分别放到两个数组中。然后先将奇数数组放到原先数组中，紧接着将偶数数组放到先前数组中。
时间复杂度：O(N)
空间复杂度：O(N)

代码：

public class Solution {public void reOrderArray(int [] array) {int i=0, j=0, k=0, begin=0;int[] odd = new int[array.length];  // 奇数int[] even = new int[array.length];for(i=0;i<array.length;i++) {if(array[i]%2==0) {  // 拷贝偶数even[k] = array[i];k++;}if(array[i]%2==1) {  // 拷贝奇数odd[j] = array[i];j++;}} for(i=0;i<j;i++) {array[i] = odd[i];  // 拷贝奇数}for(i=j,begin=0;begin<k;begin++,i++) {array[i] = even[begin];  // 拷贝偶数}}
}

测试程序：

import java.util.Scanner;class Solution {public void reOrderArray(int [] array) {int i=0, isOdd=0, isEven=0;int[] even = new int[array.length];  // 偶数for(i=0;i<array.length;i++) {if(array[i]%2==1) {array[isOdd++] = array[i];}if(array[i]%2==0) {even[isEven++] = array[i];}}for(i=isOdd, isEven=0;i<array.length;i++,isEven++) {array[i] = even[isEven];}}
}public class Main {public static void main(String[] args) {int row=0, col=0;int[] arr = new int[4];Solution s = new Solution();Scanner sc = new Scanner(System.in);for(row=0;row<arr.length;row++) {arr[row]= sc.nextInt();}s.reOrderArray(arr);for(int i=0;i<arr.length;i++) {System.out.print(arr[i]+" ");}		sc.close();}
}

# Input
1 2 3 4
# Output
1 3 2 4

版本2

思路：对数组进行遍历，遇到奇数放到原本数组中，从前往后；遇到偶数存下来，遍历完成后，将存下的偶数依次放入原数组奇数结束的位置。
优点：对版本1做了优化，减少了n空间申请。
时间复杂度：O(N)
空间复杂度：O(N)

代码：

public class Solution {public void reOrderArray(int [] array) {int i=0, isOdd=0, isEven=0;int[] even = new int[array.length];  // 偶数for(i=0;i<array.length;i++) {    	   	if(array[i]%2==1) {array[isOdd++] = array[i];} else if(array[i]%2==0) {even[isEven++] = array[i];}    		}for(i=isOdd, isEven=0;i<array.length;i++,isEven++) {array[i] = even[isEven];}}
}

版本3 插入排序

思路：对数组进行遍历，遇到奇数，就将前面的偶数后移。奇数的个数同时记录下来，指示后面奇数该放的位置。
缺点：对版本2做了优化，减少了n空间申请，但是时间复杂度上升。。
时间复杂度：O( N 2 N^2 N2)
空间复杂度：O(1)

代码：

public class Solution {public void reOrderArray(int [] array) {int i=0, j=0, oddCnt=0, odd=0;for(i=0;i<array.length;i++) {if(array[i]%2==1) {odd = array[i];for(j=i;j>oddCnt;j--) {array[j] = array[j-1];}array[j] = odd;oddCnt++;}}}
}

版本4 冒泡排序

思路：从后往前冒泡，当相近结点 & 前偶后奇 时，则进行交换。
时间复杂度：O( N 2 N^2 N2)
空间复杂度：O(1)

代码：

public class Solution {public void reOrderArray(int [] array) {int i=0, j=0, tmp=0, odd=0;for(i=0;i<array.length;i++) {for(j=array.length-1;j>i;j--) {if( ((array[j]&1)==1) && ((array[j-1]&1)==0) ) {tmp = array[j];array[j] = array[j-1];array[j-1] = tmp;} 				}}}
}

三、小结

排序算法还是能用的上的，具体的算法可能需要对应场景略加修改，但是思想不变，继续加油！^_

四、参考

1、[编程题]调整数组顺序使奇数位于偶数前面

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！