wordpress主页删除/seo上排名

调整数组顺序使奇数位于偶数之前

题目描述：

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

 示例

示例1：

输入：[1,2,3,4]

返回值：[1,3,2,4]

示例2：

输入：[1,2,3,4,5,6,7]

输出：[1,3,5,7,2,4,6]

 思路：

1. 不考虑时间复杂度，最简单的思路就是从头扫描数组，每碰到一个偶数，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，此时把该偶数放入这个空位。时间复杂度：O(n^2)
2. 维护两个指针
   • 第一个指针初始化时指向数组的第一个元素，只向后移动；
   • 第二个指针指向数组的最后一个元素，指向前移动。
   • 只要第一个指针位于第二个指针之前，如果第一个指针指向的数字是偶数，第二个指针指向的数字是奇数，则交换这两个数字。
3. 如果要保证奇数与奇数，偶数与偶数之间的相对位置不变；借鉴冒泡排序，将相邻的偶数与奇数交换

代码实现：

双指针

public class Solution {public  static int[] reOrderArray (int[] array) {//奇数在前，偶数在后/*** 使用左右指针，不能保证保持原来的顺序*/int i =0;int j = array.length-1;while (i < j){while (i < j&& array[i] %2 != 0 ){i++;}while (i < j&& array[j] %2 == 0 ){j--;}if (i < j){int temp = array[i];array[i] = array[j];array[j] = temp;}}return array;}public static void main(String[] args) {int[] array = {1,2,3,4,5,6,7};int[] results = reOrderArray(array);for (int i :results){System.out.println(i);}}
}

实际输出结果：

预期输出结果：

使用上述方法得到的结果，没有保持相对位置不变

相邻的偶数与奇数交换

public class Solution {public  static int[] reOrderArray (int[] array) {//奇数在前，偶数在后/***借鉴冒泡排序，将相邻的偶数和奇数交换*/for (int i=1;i< array.length;i++){for (int j =i-1;j>=0;j--){if ( array[j] %2 == 0 && array[j+1] %2 ==1 ){int temp = array[j];array[j] =array[j+1];array[j+1] = temp;}}}return array;}
}

扩展

扩展题目：

1. 数组中的数按照大小分为两部分，所有辅助都在非负数的前面。
2. 数组中的数分为两部分，能被3整除的数都在不能不能被3整除的数的前面。

针对这一系列同类型的问题：

把整个函数分解为两个部分；

一是判断数字应该在前半部分还是后半部分的标准；

二是拆分数组的操作。

代码上只需要调整分组的标准isEven函数，其他代码不需要改动。

提高了代码的重用性，更好的扩展功能。

public class Solution {public int[] reOrderArray (int[] array) {int length =array.length;if (array == null || length == 0) {return null;}int i = 0;int j = array.length-1;while (i < j){while (i < j && !isEven(array[i])){i++;}while (i < j && isEven(array[j])){j--;}if (i < j){int temp =array[i];array[i] = array[j];array[j] = temp;}}return array;}//确定分组的标准private boolean isEven(int n) {return (n & 1) == 0;}
}