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

题目描述

需要保证奇数和奇数，偶数和偶数之间的相对位置不变，这和书本不太一样。

解题思路

方法一：

创建一个新数组，时间复杂度 O(N)，空间复杂度 O(N)。

package 剑指offer.调整数组顺序使奇数位于偶数前面_21;/* 作者     :XiangLin 创建时间 :13/06/2020 14:17 文件     :OrderArray.java IDE      :IntelliJ IDEA */ import java.util.Arrays; public class OrderArray { public int[] reOrderArray(int[] nums){ //奇数个数 int oddCnt = 0; for(int x: nums){ if (!isEven(x)){                 oddCnt++; } } int[] copy =  nums.clone(); int i = 0, j = oddCnt; for (int num : copy){ if (num % 2 == 1)                 nums[i++] = num; else                 nums[j++] = num; } return nums; } private boolean isEven(int x){ return x % 2 == 0; } public static void main(String[] args) { int nums[] = {1,2,3,4,5};         OrderArray o = new OrderArray(); int[] data = o.reOrderArray(nums);         System.out.println(Arrays.toString(data)); } } 

方法二：

使用冒泡思想，每次都将当前偶数上浮到当前最右边。时间复杂度 O(N2)，空间复杂度 O(1)，时间换空间。

package 剑指offer.调整数组顺序使奇数位于偶数前面_21;/* 作者     :XiangLin 创建时间 :13/06/2020 14:39 文件     :OrderArray2.java IDE      :IntelliJ IDEA */ import java.util.Arrays; public class OrderArray2 { public int[] reOrderArray(int[] nums){ int N = nums.length; for (int i = N - 1; i > 0; i --){ for (int j = 0; j < i; j++){ if (isEven(nums[i]) && !isEven(nums[j + 1])){ swap(nums,j,j+1); } } } return nums; } private boolean isEven(int x){ return x % 2 == 0; } private void swap(int[] nums, int i ,int j){ int t = nums[i];         nums[i] = nums[j];         nums[j] = t; } public static void main(String[] args) { int nums[] = {1,2,3,4,5};         OrderArray2 o = new OrderArray2(); int[] data = o.reOrderArray(nums);         System.out.println(Arrays.toString(data)); } } 

另外博主这些年来看过或者听过的一些不错的常用的上千本书籍，没准你想找的书就在这里呢，包含了互联网行业大多数书籍和面试经验题目等等。有人工智能系列（常用深度学习框架TensorFlow、pytorch、keras。NLP、机器学习，深度学习等等），大数据系列(Spark,Hadoop,Scala,kafka等)，程序员必修系列（C、C++、java、数据结构、linux，设计模式、数据库等等）以下是部分截图

更多文章见本原创微信公众号「五角钱的程序员」，我们一起成长，一起学习。一直纯真着，善良着，温情地热爱生活。关注回复【电子书】即可领取哦。

给大家推荐一个Github,上面非常非常多的干货：https://github.com/XiangLinPro/IT_book

There is no such thing as a great talent without great will – power.——Balzac
「没有伟大的意志力，便没有雄才大略。——巴尔扎克」

关于Datawhale

Datawhale是一个专注于数据科学与AI领域的开源组织，汇集了众多领域院校和知名企业的优秀学习者，聚合了一群有开源精神和探索精神的团队成员。Datawhale以“for the learner，和学习者一起成长”为愿景，鼓励真实地展现自我、开放包容、互信互助、敢于试错和勇于担当。同时Datawhale 用开源的理念去探索开源内容、开源学习和开源方案，赋能人才培养，助力人才成长，建立起人与人，人与知识，人与企业和人与未来的联结。

2020.6.13城口