1

问答题 1 /50

仅用O(1)的空间,将整数数组按奇偶数分成2部分,数组左边是奇数、右边是偶数。(要求:给出完整代码,尽量高效,简洁)

参考答案

#两个指针,分别从头和从尾遍历数组,详见代码,已测试通过
#include <stdio.h>
#include <stdlib.h>
#define bool int
#define false 0
#define true 1
void Reorder(int *pData, unsigned int length, bool (*func)(int));
bool isEven(int n);
void ReorderOddEven_1(int *pData, unsigned int length)
{
    if(pData == NULL || length == 0)
        return;
    int *pBegin = pData;
    int *pEnd = pData + length - 1;
    while(pBegin < pEnd)
    {
        // 向后移动pBegin,直到它指向偶数
        while(pBegin < pEnd && (*pBegin & 0x1) != 0)
            pBegin ++;
        // 向前移动pEnd,直到它指向奇数
        while(pBegin < pEnd && (*pEnd & 0x1) == 0)
            pEnd --;
        if(pBegin < pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}
void Reorder(int *pData, unsigned int length, bool
  (*func)(int))
{
    if(pData == NULL || length == 0)
        return;
    int *pBegin = pData;
    int *pEnd = pData + length - 1;
    while(pBegin < pEnd) 
    {
        //向后移动pBegin
        while(pBegin < pEnd &&!func(*pBegin))
            pBegin ++;
        // 向前移动pEnd
        while(pBegin < pEnd &&func(*pEnd))
            pEnd --;
        if(pBegin < pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}
bool isEven(int n)
{
    return (n & 1) == 0;
}