剑指Offer(13)调整数组顺序使奇数位于偶数前面

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

用空间换时间做法&＃xff0c;就是新建一个数组&＃xff0c;copy一份&＃xff0c;先计算出奇数的个数&＃xff0c;也就是能够知道第一个偶数应该放在数组的哪一个位置&＃xff0c;然后再遍历一次&＃xff0c;依次放到对应的位置即可。

public class Solution {public void reOrderArray(int[] nums) {// 奇数个数int oddCnt &＃61; 0;for (int x : nums)if (x % 2 &＃61;&＃61; 1)oddCnt&＃43;&＃43;;int[] copy &＃61; nums.clone();int i &＃61; 0, j &＃61; oddCnt;for (int num : copy) {if (num % 2 &＃61;&＃61; 1)nums[i&＃43;&＃43;] &＃61; num;elsenums[j&＃43;&＃43;] &＃61; num;}}
}


第二种做法&＃xff0c;时间复杂度为O(n^2),类似冒泡&＃xff0c;将找到的奇数不断往前面冒泡&＃xff0c;直到前面排好奇数的位置。

public class Solution {public void reOrderArray(int [] array) {// 已经摆好的奇数个数int numOfOdd &＃61; 0;for (int i &＃61; 0; i < array.length; i&＃43;&＃43;) {if (array[i] % 2 &＃61;&＃61; 1) {int j &＃61; i;// 往前面冒泡while (j > numOfOdd) {int tmp &＃61; array[j];array[j] &＃61; array[j-1];array[j-1] &＃61; tmp;j--;}numOfOdd&＃43;&＃43;;}}}
}


此文章仅代表自己&＃xff08;本菜鸟&＃xff09;学习积累记录&＃xff0c;或者学习笔记&＃xff0c;如有侵权&＃xff0c;请联系作者删除。人无完人&＃xff0c;文章也一样&＃xff0c;文笔稚嫩&＃xff0c;在下不才&＃xff0c;勿喷&＃xff0c;如果有错误之处&＃xff0c;还望指出&＃xff0c;感激不尽~

技术之路不在一时&＃xff0c;山高水长&＃xff0c;纵使缓慢&＃xff0c;驰而不息。

公众号&＃xff1a;秦怀杂货店