// Given a pivot x, and a list lst, partition the list into three parts.
// The first part contains all elements in lst that are less than x
// The second part contains all elements in lst that are equal to x
// The third part contains all elements in lst that are larger than x
// Ordering within a part can be arbitrary.
// For example, given x = 10 and lst = [9, 12, 3, 5, 14, 10, 10],
// one partition may be `[9, 3, 5, 10, 10, 12, 14].
#include <iostream>
#include <string>
#include <list>
#include <vector>
using namespace std;
list<int> PartitionList(int x, list<int> lst)
{
list<int> newList = list<int>();
vector<int> front = vector<int>(), middle = vector<int>(), back = vector<int>();
list<int>::iterator it;
for (it = lst.begin(); it != lst.end(); ++it)
{
if (*it < x)
{
//cout << *it << endl;
front.push_back(*it);
}
else if (*it > x)
{
//cout << *it << endl;
back.push_back(*it);
}
else // the value is equal to x
{
//cout << *it << endl;
middle.push_back(*it);
}
}
for (int i = 0; i < front.size(); ++i)
newList.push_back(front[i]);
for (int i = 0; i < middle.size(); ++i)
newList.push_back(middle[i]);
for (int i = 0; i < back.size(); ++i)
newList.push_back(back[i]);
return newList;
}
int main()
{
list<int> lst { 9, 12, 3, 5, 14, 10, 10 };
int x = 10;
lst = PartitionList(x, lst);
list<int>::iterator it;
for (it = lst.begin(); it != lst.end(); ++it)
{
cout << *it << ", ";
}
return 0;
}
Comentários