【原】精选算法题(3)——奇偶数据分离

翟天保的图书馆 2022-03-31

展开全文

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

解题思路：

本题题目简单，但可以拓展一下思路。我用了三种方法，分别是vector存储、list存储、自定义链表存储，以验证计算效率。三种方法均采用遍历思路，遍历过程中将奇数存储在一个容器中，将偶数存储在另一个容器中，然后两容器合并即可。其中，我自定义了一个链表，将奇数链表的尾巴和偶数链表的头进行连接，节省了合并容器的过程，且具备较高的插入效率。文章后续有完整的速度对比方案。

测试代码：

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <time.h>
#include <list>

using namespace std;

struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};

// 判断是否为奇数
bool isOdd(int number)
{
return (bool)(number % 2);
}

// 奇数偶数分离
vector<int> OddEvenSeparate1(vector<int> input)
{
vector<int> output;
vector<int> evens;
for (int i = 0; i < input.size(); ++i)
{
if (isOdd(input[i]))
{
output.emplace_back(input[i]);
}
else
{
evens.emplace_back(input[i]);
}
}
output.insert(output.end(), evens.begin(), evens.end());
return output;
}

// 奇数偶数分离
list<int> OddEvenSeparate2(vector<int> input)
{
list<int> output;
list<int> evens;
for (int i = 0; i < input.size(); ++i)
{
if (isOdd(input[i]))
{
output.emplace_back(input[i]);
}
else
{
evens.emplace_back(input[i]);
}
}
output.splice(output.end(), evens);
return output;
}

// 奇数偶数分离
ListNode* OddEvenSeparate3(vector<int> input)
{
ListNode* output = new ListNode(-1);
ListNode* evens = new ListNode(-1);
ListNode* ohead = output;
ListNode* ehead = evens;
for (int i = 0; i < input.size(); ++i)
{
if (isOdd(input[i]))
{
ListNode* temp = new ListNode(input[i]);
output->next = temp;
output = output->next;
}
else
{
ListNode* temp = new ListNode(input[i]);
evens->next = temp;
evens = evens->next;
}
}
ohead = ohead->next;
ehead = ehead->next;
output->next = ehead;
return ohead;
}

int main()
{
// 给定数组
vector<int> a(10000);
for (int i = 0; i < a.size(); ++i)
{
a[i] = rand();
}
clock_t s, e;
// 奇数偶数分离
// 第一种方法
s = clock();
vector<int> b1 = OddEvenSeparate1(a);
e = clock();
cout << "time1:" << e - s << endl;
cout << "first:" << endl;
for (auto i : b1)
{
cout << i << " ";
}
cout << endl;
// 第二种方法
s = clock();
list<int> b2 = OddEvenSeparate2(a);
e = clock();
cout << "time2:" << e - s << endl;
cout << "second:" << endl;
for (auto i : b2)
{
cout << i << " ";
}
cout << endl;
// 第三种方法
s = clock();
ListNode* b3 = OddEvenSeparate3(a);
e = clock();
cout << "time3:" << e - s << endl;
cout << "third:" << endl;
while (b3 != nullptr)
{
cout << b3->val << " ";
b3 = b3->next;
}
cout << endl;

system("pause");
return 0;
}