21、调整数组顺序是奇数位于偶数前面
目录
题目描述
测试用例
题目考点
解题思路
只完成基本功能的解法
考虑可扩展的解法
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
测试用例
- 功能测试（输入数组中的奇数、偶数交替出现；输入的数组中所有偶数都出现在奇数的前面；输入的数组所有奇数都出现在偶数的前面）
- 特殊输入测试（输入空指针；输入的数组只包含一个数字）
题目考点
- 考察应聘者的快速思维能力。
- 对于已经工作几年的应聘者，面试官还将考察其对扩展性的理解，要求应聘者写出的代码具有可重用性。
解题思路
只完成基本功能的解法
维护连个指针：
第一个指针初始化时指向数组的第一个数字，它只向后移动；
第二个指针指向数组的最后一个数字，它只向前移动。
在两个指针相遇之前，第一个指针总是位于第二个指针前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，则交换这两个数字。
PS：为了避免重复交换，我们可以在可能交换之前，让两个指针分别向自己的方向扫描，直到第一个指针指向偶数，第二个指针指向奇数。
/*** 调整数组顺序使奇数位于偶数前面*/
public class Solution1 {/*** 只完成基本功能的解法* @param array*/public void reOrderArray(int [] array) {// 防止特殊输入if (array == null || array.length == 0) {return;}int i = 0;int j = array.length-1;while (i < j) {// 第一个指针，直到遇见偶数，然后开始准备交换while (i < j && (array[i] & 1) != 0) {i++;}// 第二个指针，直到遇见奇数，然后开始准备交换while (i < j && (array[j] & 1) == 0) {j--;}// 开始交换if (i < j) {swapArray(array, i, j);}}}/*** 交换数组的两个值* @param array* @param i* @param j*/public void swapArray(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}}考虑可扩展的解法
这到题目是要求我们按照奇偶分类，如果我们要按照正负分类，我们第一反应应该是去该代码，但是这样很不好。耦合度太高，所以我们需要考虑扩展性。这里我们是可以使用 策略模式。策略模式
package Sword;
/*** 策略模式实现数组重排成两部分* 定义条件--->触发条件发生行为---->行为* @author tyler**/
public class Reorder {private ReorderStrategy reorderStrategy; // 重排序策略对象public Reorder(ReorderStrategy reorderStrategy) {// TODO Auto-generated constructor stub 解决办法构造器this.reorderStrategy = reorderStrategy;}// ----------基本功能模块---------------public void reOrderArray(int[] array) {// 异常处理if (array == null || array.length == 0) {return;}int i = 0;int j = array.length - 1;while (i < j) {// 前指针，直到遇到交换条件(直到为偶数)，然后准备开始交换while (i < j && !reorderStrategy.recorderBySomething(array, i)) {i++;}// 后指针，直到交换条件（直到为奇数），然会准备开始交换while (i < j && reorderStrategy.recorderBySomething(array, j)) {j--;}// 触发了条件，操作：交换if (i < j) {int temp = array[i];array[i] = array[j];array[j] = temp;}}}// ---- 主函数调用实现----------public static void main(String[] args) {int[] array = new int[] {1,2,3,4,5};ReorderStrategy reorderStrategy = new isEven(); // 策略对象选择具体策略类Reorder reorder = new Reorder(reorderStrategy); // 策略对象传入实现类reorder.reOrderArray(array); // 实现类调用功能模块for (int i = 0; i < array.length; i++) {System.out.print(array[i]);}}
}/*** 接口：重排序策略*/
interface ReorderStrategy{boolean recorderBySomething(int[] array, int index);
}/**
* 具体策略：实现接口
* 返回是否为偶数
*/
class isEven implements ReorderStrategy{@Overridepublic boolean recorderBySomething(int[] array, int index) {// TODO Auto-generated method stubreturn (array[index] & 1) == 0; // 相与为0则为偶数，10 & 01=0 }
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！