29.调整数组顺序使奇数位于偶数前面[ReOrderArray]

【题目】

输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

分析】

如果不考虑时间复杂度,最简单的思路应该是从头扫描这个数组,每碰到一个偶数时,拿出这个数字,并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位,这时把该偶数放入这个空位。由于碰到一个偶数,需要移动O(n)个数字,因此总的时间复杂度是O(n2)。

要求的是把奇数放在数组的前半部分,偶数放在数组的后半部分,因此所有的奇数应该位于偶数的前面。也就是说我们在扫描这个数组的时候,如果发现有偶数出现在奇数的前面,我们可以交换他们的顺序,交换之后就符合要求了。

因此我们可以维护两个指针,第一个指针初始化为数组的第一个数字,它只向后移动;第二个指针初始化为数组的最后一个数字,它只向前移动。在两个指针相遇之前,第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数,我们就交换这两个数字。

代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 

// Reorder an array so that all odd numbers are before even numbers
bool IsEven(int n)
{
    
return n & 1 == 0;
}

void ReOrder(int a[], int n, bool (*func)(int))
{
    
if (NULL == a || n <= 0 || NULL == func)
        
return;
    
int left = 0, right = n - 1;
    
while(left < right)
    {
        
while(!func(a[left]))
            left++;
        
while(func(a[right]))
            right--;
        
if (left < right)
            myswap(a[left], a[right]);
    }
}

【参考】

http://zhedahht.blog.163.com/blog/static/25411174200741295930898/

个人学习笔记,欢迎拍砖!---by hellogiser

Author: hellogiser
Warning: 本文版权归作者和博客园共有,欢迎转载,但请保留此段声明,且在文章页面明显位置给出原文连接。Thanks!
Me: 如果觉得本文对你有帮助的话,那么【推荐】给大家吧,希望今后能够为大家带来更好的技术文章!敬请【关注】
原文地址:https://www.cnblogs.com/hellogiser/p/3738854.html