By

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考

题目

奇数偶数分离 奇数在左侧  偶数在右侧 要求复杂度为O(N)

解析

本题的难点主要是在O(N)复杂度的要求，但是想想有没有类似对数组左右分离的操作？
对，就是快速排序，在使用快速排序的分区中左边都是小于基准，右边都是大于基准
所以，同理，现在按照快排分区的思想，左边都是为奇数，右边都是为偶数，基数无论为奇偶皆可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 使用快速排序的分区思想，只是<和>变为奇数和偶数而已
 * @param a
 */
public static void oddEvenSplit(int[] a)
{
	if(a.length<2)
		return ;
	
	int k=a[0],i=0,j=a.length-1;
	while(i<j)
	{
		while((a[j]&1)==0 && i<j)//从右往左找  直到遇到奇数
			j--;
		a[i]=a[j];
		
		while((a[i]&1)==1 && i<j)//从左往右找  直到遇到偶数
			i++;
		a[j]=a[i];
	}
	a[i]=k;
}

可以看下测试代码：

1
2
3
4
5
6
7
public static void main(String[] args) {
	int[] a={1,2,3,4,5,6,7,8};
	oddEvenSplit(a);
	
	for(int i=0;i<a.length;i++)
		System.out.print(a[i]);
}

输出的结果为：

75314628

可以发现这里是以1为基准，1左边的都是奇数，1右边的都是偶数

参考

July微软100道面试题 忘了第哪一道 -_-

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考