剑指offer（第二版）——调整数组顺序使奇数位于偶数前面
PS：《剑指offer》是很多同学找工作都会参考的一本面试指南，同时也是一本算法指南（为什么它这么受欢迎，主要应该是其提供了一个循序渐进的优化解法，这点我觉得十分友好）。现在很多互联网的算法面试题基本上可以在这里找到影子，为了以后方便参考与回顾，现将书中例题用Java实现（第二版），欢迎各位同学一起交流进步。
GitHub： https://github.com/Uplpw/SwordOffer。
剑指offer完整题目链接： https://blog.csdn.net/qq_41866626/article/details/120415258
目录
- 1 题目描述
- 2 测试用例
- 3 思路
- 4 代码
1 题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
leetcode链接： 调整数组顺序使奇数位于偶数前面（以下代码已测试，提交通过）
2 测试用例
一般是考虑功能用例，特殊（边缘）用例或者是反例，无效测试用例这三种情况。甚至可以从测试用例寻找一些规律解决问题，同时也可以让我们的程序更加完整鲁棒。
（1）功能用例：正常的数组（有奇数，有偶数）。
（2）边缘用例：只有奇数，只有偶数。
（3）无效用例：数组为空。
3 思路
分析：
-
解法1：最直接也最直观的做法是，遍历数组，遇到偶数将其拿出来，先将后面的元素往前移动，在把偶数放到最后。但是复杂度比较高 O ( n 2 ) O(n^2) O(n2)
-
解法2：用双指针从两端向中间扫描，处理过程与快排很相似，时间复杂度o(n)，这应该是最快的解法了。思路简单，就当复习下快排吧。
-
剑指offer书中提到了一点，是将判断部分写成函数，这样能够提升代码的可扩展性，这一类问题（非负数在前，负数在后；能被3整除的在前，不能的在后；）都只需修改下判断函数即可解决。（在Java实现中，需要定义一个该方法的接口，然后创建实现该接口的类，并根据需要实现该方法。最后只需要传入接口类型的参数并调用方法即可）
4 代码
算法实现：
public class ReorderArray {public static int[] exchange(int[] nums) {if (nums == null || nums.length == 0) {return nums;}int length = nums.length;int start = 0;int end = length - 1;while (start < end) {if (flag(nums, start, end)) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;} else {if ((nums[start] & 1) == 1) {start++;}if ((nums[end] & 1) == 0) {end--;}}}return nums;}public static boolean flag(int[] nums, int start, int end) {// 前面是偶数，后面是奇数，返回true调整顺序if ((nums[start] & 1) == 0 && (nums[end] & 1) == 1) {return true;}return false;}public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5, 7, 7};int[] data = exchange(nums);for (int i = 0; i < data.length; i++) {System.out.print(data[i] + "\t");}System.out.println();}
}
参考
在解决本书例题时，参考了一些大佬的题解，比如leetcode上的官方、K神，以及其他的博客，在之后的每个例题详解后都会给出参考的思路或者代码链接，同学们都可以点进去看看！
本例题参考：
- https://www.jianshu.com/p/3c332f879722
本文如有什么不足或不对的地方，欢迎大家批评指正，最后希望能和大家一起交流进步、拿到心仪的 offer !!!
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！