题目
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入： nums = [1,2,3,4]
输出： [1,3,2,4]
注： [3,1,2,4] 也是正确的答案之一。
提示：
1 <= nums.length <= 50000
1 <= nums[i] <= 10000
实现方法
方法 1
思路
看到题目首先想到的暴力法，遍历数组，分别将奇偶数存入不同的列表中，然后定义一个数组，先后将存放奇偶数的列表中的元素加到数组中返回即可，主要进行的是遍历操作，所以最终复杂度为 O ( n ) O(n)O(n)；
实现
public int[] exchange(int[] nums) { // 存放最终结果 int[] result = new int[nums.length]; // 存放偶数 ArrayList<Integer> listEven = new ArrayList<>(); // 存放奇数 ArrayList<Integer> listOdd = new ArrayList<>(); // 遍历数组，将元素分别存入列表中 for(int num : nums){ if(num % 2 == 0){ listEven.add(num); }else{ listOdd.add(num); } } // 分别将奇数和偶数存入最终结果数组 for(int i = 0;i < listOdd.size(); i++){ result[i] = listOdd.get(i); } for(int i = listOdd.size(); i < listEven.size() + listOdd.size(); i++){ result[i] = listEven.get(i - listOdd.size()); } return result; }
方法 2
思路
双指针，用两个指针来获取最终结果，快的指针用来遍历数组，而慢的指针则用来指向最终结果数组存入多少个元素，主要操作是进行了两次遍历操作，所以时间复杂度为 2 O ( n ) = O ( n ) 2O(n) = O(n)2O(n)=O(n);
实现
public int[] exchange(int[] nums) { // 存放最终结果 int[] result = new int[nums.length]; int index = 0; // 第一遍遍历，将奇数加入最终结果数组 for(int num : nums){ if(num % 2 != 0){ result[index++] = num; } } // 第二遍遍历，将偶数加入最终结果数组 for(int num : nums){ if(num % 2 == 0){ result[index++] = num; } } return result; }