题解 | #调整数组顺序使奇数位于偶数前面(二)#
调整数组顺序使奇数位于偶数前面(二)
http://www.nowcoder.com/practice/0c1b486d987b4269b398fee374584fc8
题目的主要信息：
- 输入一个长度为的数组，经过调整使所有的奇数在前半部分，所有的偶数在后半部分
- 奇数与奇数之间、偶数与偶数之间的相对位置关系不固定
举一反三：**
学习完本题的思路你可以解决如下题目：
方法一：双指针复制法（推荐使用）
知识点：双指针
双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。
思路：
既然要把所有的奇数放在数组前面，所有的偶数放在数组后面，那可以统计奇数在原数组中出现了多少次，这样就可以找到二者的分界线。
有了分界线以后，前面就是奇数，后面就是偶数，可以利用两个指针分别指向二者的开头，遇到一个元素就添加到相应位置，然后指针移动。
（该方法保证了相对位置不变）
具体做法：
- step 1：遍历数组，统计奇数出现的次数，即找到了偶数开始的位置。
- step 2：准备一个和原数组同样长的新数组承接输出，准备双指针，x指向奇数开始的位置，y指向偶数开始的位置。
- step 3：遍历原数组，遇到奇数添加在指针x后面，遇到偶数添加在指针y后面，直到遍历结束。
图示：
Java实现代码：
import java.util.*;
public class Solution {
public int[] reOrderArrayTwo (int[] array) {
int n = array.length;
int[] res = new int[n];
//统计奇数个数
int odd = 0;
//遍历统计
for(int i = 0; i < n; i++){
if(array[i] % 2 == 1)
odd++;
}
//x与y分别表示答案中奇偶数的坐标
int x = 0, y = odd;
for(int i = 0; i < n; i++){
//奇数在前
if(array[i] % 2 == 1){
res[x] = array[i];
x++;
//偶数在后
}else{
res[y] = array[i];
y++;
}
}
return res;
}
}
C++实现代码：
class Solution {
public:
vector<int> reOrderArrayTwo(vector<int>& array) {
int n = array.size();
vector<int> res(n);
//统计奇数个数
int odd = 0;
//遍历统计
for(int i = 0; i < n; i++){
if(array[i] % 2)
odd++;
}
//x与y分别表示答案中奇偶数的坐标
int x = 0, y = odd;
for(int i = 0; i < n; i++){
//奇数在前
if(array[i] % 2){
res[x] = array[i];
x++;
//偶数在后
}else{
res[y] = array[i];
y++;
}
}
return res;
}
};
Python实现代码：
class Solution:
def reOrderArrayTwo(self , array: List[int]) -> List[int]:
n = len(array)
res = [0 for i in range(n)]
#统计奇数个数
odd = 0
#遍历统计
for a in array:
if a % 2:
odd += 1
#x与y分别表示答案中奇偶数的坐标
x = 0
y = odd
for a in array:
#奇数在前
if a % 2:
res[x] = a
x += 1
#偶数在后
else:
res[y] = a
y += 1
return res
复杂度分析：
- 时间复杂度：，其中为数组的长度，遍历2次数组
- 空间复杂度：，res数组属于返回函数必要数组，不算额外空间
方法二：双指针交换法（扩展思路）
思路：
这道题不需要要求相对位置不变，因此我们可以采用位置交换的方法，只要奇数全部换到前面就可以了。
利用左右双指针分别从数组首尾出发向中间走，交换其中的偶数在前奇数在后的情况。
（该方法不能保证相对位置不变）
具体做法：
- step 1：准备双指针从首尾开始，相互对撞。
- step 2：如果左右都是奇数，说明左边没问题，因为奇数要在左边，因此左指针右移，右指针暂时不动。
- step 3：如果左奇数右偶数，符合要求，左右指针都向中间走。
- step 4：如果左偶数右奇数，符合要交换的条件，将偶数换到后面，奇数换到前面。
- step 5：如果左右都是偶数，只移动右指针，右边是偶数一定正确，指针左移，但是左边需要待定，于是暂时不动。
- step 6：两指针相遇时就一定能保证左指针以左一定是奇数，右指针以右一定是偶数，做到了调整数组顺序使奇数位于偶数前面。
Java实现代码：
import java.util.*;
public class Solution {
public int[] reOrderArrayTwo (int[] array) {
//双指针
int i = 0;
int j = array.length - 1;
//向中间聚合
while(i < j){
//左右都是奇数，左移右不动
if(array[i] % 2 == 1 && array[j] % 2 == 1)
i++;
//左奇数右偶数，左右都向中间缩
else if(array[i] % 2 == 1 && array[j] % 2 == 0){
i++;
j--;
}
//左偶右奇数
else if(array[i] % 2 == 0 && array[j] % 2 == 1){
//交换
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//左右都是偶数，只移动右指针
else
j--;
}
return array;
}
}
C++实现代码：
class Solution {
public:
vector<int> reOrderArrayTwo(vector<int>& array) {
//双指针
int i = 0;
int j = array.size() - 1;
//向中间聚合
while(i < j){
//左右都是奇数，左移右不动
if(array[i] % 2 == 1 && array[j] % 2 == 1)
i++;
//左奇数右偶数，左右都向中间缩
else if(array[i] % 2 == 1 && array[j] % 2 == 0)
i++, j--;
//左偶右奇数
else if(array[i] % 2 == 0 && array[j] % 2 == 1)
//交换
swap(array[i], array[j]);
//左右都是偶数，只移动右指针
else
j--;
}
return array;
}
};
Python实现代码：
class Solution:
def reOrderArrayTwo(self , array: List[int]) -> List[int]:
#双指针
i = 0
j = len(array) - 1
#向中间聚合
while i < j:
#左右都是奇数，左移右不动
if array[i] % 2 == 1 and array[j] % 2 == 1:
i += 1
#左奇数右偶数，左右都向中间缩
elif array[i] % 2 == 1 and array[j] % 2 == 0:
i += 1
j -= 1
#左偶右奇数
elif array[i] % 2 == 0 and array[j] % 2 == 1:
#交换
temp = array[i]
array[i] = array[j]
array[j] = temp
#左右都是偶数，只移动右指针
else:
j -= 1
return array
复杂度分析：
- 时间复杂度：，其中为数组的长度，双指针最多只遍历数组一次
- 空间复杂度：，常数级变量，无额外辅助空间
投递华为等公司10个岗位