首页 > 代码库 > 【面试题014】调整数组顺序使奇数位于偶数前面

【面试题014】调整数组顺序使奇数位于偶数前面

2024-07-02 17:10:22   229人阅读

【面试题014】调整数组顺序使奇数位于偶数前面 

 

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数     位于    数组的前半部分，所有偶数位于数组的后半部分。

 

1.第一个指针初始化为指向数组的第一个数字，他向后移动

2.第二个指针初始化为指向数组的最后一个数字，他向前面移动，

3.在两个指针相遇之前，第一个指针总是位于第二个指针的前面，

4.如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，

我们就交换两个数字，否者如果是一个满足，或者都不满足就按照规则移动指针；

 

Reorder.cpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
  
#include <iostream>
#include <cstdio>

using namespace std;

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 ReorderOddEven_2(int *pData, unsigned int length)
{
    Reorder(pData, length, isEven);
}

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;
}

/*测试代码*/
void PrintArray(int numbers[], int length)
{
    if(length < 0)
        return;

    for(int i = 0; i < length; ++i)
        printf("%d\t", numbers[i]);

    printf("\n");
}

void Test(int numbers[], int length)
{
    int *copy = new int[length];
    for(int i = 0; i < length; ++i)
    {
        copy[i] = numbers[i];
    }

    printf("Test for solution 1:\n");
    PrintArray(numbers, length);
    ReorderOddEven_1(numbers, length);
    PrintArray(numbers, length);

    printf("Test for solution 2:\n");
    PrintArray(copy, length);
    ReorderOddEven_2(copy, length);
    PrintArray(copy, length);

    delete[] copy;
}

int main()
{
    int numbers[] = {1, 2, 3, 4, 5, 6, 7};
    Test(numbers, sizeof(numbers) / sizeof(int));
    return 0;
}

运行结果：

Test for solution 1:
1 2 3 4 5 6 7
1 7 3 5 4 6 2
Test for solution 2:
1 2 3 4 5 6 7
1 7 3 5 4 6 2

 

Makefile:

1
2
3
4
5
6
7
8
9
10
11
12
  
.PHONY:clean  
CPP=g++  
CFLAGS=-Wall -g  
BIN=test  
OBJS=Reorder.o  
LIBS=  
$(BIN):$(OBJS)  
    $(CPP) $(CFLAGS) $^ -o $@ $(LIBS)  
%.o:%.cpp  
    $(CPP) $(CFLAGS) -c $< -o $@  
clean:  
    rm -f *.o $(BIN)  

 


联系
我们