给定一个包含n个对象的数组，其键只有四个值之一。重新排列数组，使相同类型的对象出现在一起。使用O(1)额外空间和O(n)时间。
我无法想象超过三组（荷兰国旗问题）。非常感谢您提供帮助。
例如a[6]={1,2,3,4,3,1}; 那么结果应该是{1,1,2,3,3,4}或任何顺序，只有数字分组的顺序很重要（即，结果不必按升序排列）
#include <iostream>
using namespace std;
int main() {
int a[] = {1,2,3,4,3,1,2,3,3,4};
int size = sizeof(a) / sizeof(int);
int ptr = 0;
for(int flag=1;flag <= 4;++flag){
for(int i=ptr;i<size;++i){
if(a[i] == flag){
swap(a[i],a[ptr++]);
}
}
}
for(int i=0;i<size;++i){
cout<<a[i]<<" ";
}
}
更新：
对于 独立于组数，您可以使用 trie 数据结构。Trie 由每个数字的二进制表示组成，最后一个节点保存那个组元素出现次数的计数值。
由于我们可以用32位表示整数，因此Trie占用的空间将更少，并且不会随着组数的增加而增长。
因此，空间复杂度为O（1）。时间复杂度为O（n + log（max_number）* n）。
def partition(nums):
key1_index = 0
key2_index = 0
key3_index = 0
key4_index = len(nums) - 1
while key3_index <= key4_index:
if nums[key3_index] == 1:
nums[key1_index], nums[key3_index] = nums[key3_index], nums[key1_index]
key1_index += 1
if key2_index < key1_index:
key2_index += 1
if nums[key3_index] != 2:
key3_index += 1
elif nums[key3_index] == 2:
nums[key3_index], nums[key2_index] = nums[key2_index], nums[key3_index]
key2_index += 1
key3_index += 1
elif nums[key3_index] == 3:
key3_index += 1
else:
nums[key3_index], nums[key4_index] = nums[key4_index], nums[key3_index]
key4_index -= 1
return nums
这是一个单遍 O(n) 解决方案，使用 O(1) 空间。基本思路类似于必须排序三个键的情况。第一个键是通常三个键情况下的额外复杂度。我们保留 4 个指针，每个键一个。当我们遇到一个值等于 key1 的索引时，我们将其与下一个位置交换，这个位置应该插入 key1。然后，我们递增 key1_index。现在，当我们递增 key1_index 时，这意味着我们还需要递增 key2_index，但并不总是如此。何时需要在递增 key1_index 后递增 key2_index？当 key2_index 落后于 key1_index 时。例如：
初始数组：[3, 1, 1, 2] # key1_index = 0 和 key2_index = 0
当遇到nums[1] = 1时，我们知道它需要放在key1_index = 0处。因此，我们将其放在那里，key1_index变为1。但现在，key2_index落后了。所以，我们也需要增加它。否则，当我们遇到nums[3] = 2时，它将覆盖我们刚刚放置的第一个1。
什么情况下不需要增加key2_index？当key2_index已经被增加并且具有比key1_index更大的值时。在这种情况下，即使我们遇到key1，它也不会影响key2的下一个插入位置。
key3，但不总是这样。当交换key1_index和key3_index时，我们可能会将在key1_index中的key2带到key3_index位置。例如：[1, 1, 2, 2, 3, 3, 1]
^ ^
| |
| This is where we're currently at, encountering 1.
|
This is the position where next 1 (key1) will be inserted
[1, 1, 1, 2, 3, 3, 2]
^ ^ ^
| | |
| Next 2 will be inserted here
| |
| |
| We've brought 2 here which need to be put back to their proper
| place (So we can't increment key3. Otherwise, 2 will remain here.)
|
|
1 (key1) has been put into its place
key3_index与key1_index交换，使得在key3_index处出现除了key2之外的任何东西，则我们不需要做任何事情。因为排序顺序将保持不变。为什么？请记住，key4应从数组的后面插入。如果交换将一个key3带到key3_index，这意味着在key1和key3之间没有key2。所以，我们不需要做任何事情。O(n)的DNF解决方案从最低和最高索引开始形成两个集合，并知道在它们之间形成第三个集合是同质的，因此不需要进一步处理。
如果将集合数量增加到四个或更多，则仍然可以以相同的“精神”形成顶部和底部集合，因此在O(n)时间内完成，但中间部分仍然是混合的，必须再次进行检查。这就是为什么它不再是“纯”的O(n) - 数组/序列只有两个端点。
int a[] = { 1,2,3,4,3,1,2,3,3,4 };
int size = sizeof(a) / sizeof(int);
int bottom = 0, top = size - 1;
for (int bottomband = 1, topband = 4; topband > bottomband; bottomband++, topband--) {
int i = bottom;
while (i <= top) {
if (a[i] == bottomband) {
swap(a[i], a[bottom]);
i++;
bottom++;
}
else if (a[i] == topband) {
swap(a[i], a[top]);
top--;
}
else
i++;
}
}
for (int i = 0; i<size; ++i) {
cout << a[i] << " ";
}
你可以在里面识别到“经典”的DNF循环（当topband从3开始时，它就变成了原始算法）。a[]是从另一个解决方案中取出的，以便进行比较。
swap调用的次数显示有10次，这也适用于Vivek的解决方案。这部分是巧合，部分是因为两个解决方案都愉快地交换相同的元素，因为只有“当前”元素被检查，而另一个元素（位于bottom、top或ptr）则不会被检查。例如，两个算法的第一件事情都是将列表开头的1与其自身交换。
通过跳过连续的相同元素块（在改变带和调整标记时都必须这样做），代码变得越来越长...
int bottom = 0, top = size - 1;
for (int bottomband = 1, topband = 4; topband > bottomband; bottomband++, topband--) {
while (a[bottom] == bottomband)bottom++;
while (a[top] == topband)top--;
int i = bottom;
while (i <= top) {
if (a[i] == bottomband) {
swap(a[i], a[bottom]);
i++;
bottom++; // it would be done by the next line in fact
while (a[bottom] == bottomband)bottom++;
}
else if (a[i] == topband) {
swap(a[i], a[top]);
top--; // this one too
while (a[top] == topband)top--;
}
else
i++;
}
}
...并且对swap的调用次数减少到6。虽然复杂度类别没有改变（我认为），但是对于一个可能代价高昂的操作的实际调用次数已经减少了40%。这就是理论和实践之间的差异。
让unik_elems数组包含不同的元素，其中它们之间可以进行比较。即我们可以使用<或>。例如[1,2,3,4]。
因此，如果这些是4个不同的元素，则我们可以选择第一个枢轴为2，并将1组合并到2的左侧，然后我们将枢轴更改为3并将2组合并到3的左侧，因为我们已经分组了0，所以我们将从未分组的数组开始的索引。这样，我们就可以将枢轴更改为4。假设我们首先对给定的4个不同元素进行排序。
nums = [1,4,3,2,2,3,4,1,3,2,4,1,3,2,4,1]
unclassified = 0
unik_elems = [1,2,3,4]
for pivot_idx in range(1, len(unik_elems)):
pivot = unik_elems[pivot_idx]
# we start the array from the index from where the elements are unclassified.
# Hence, when selecting 3 as pivot in this example, the elements on the left
# of unclassified will be 1 and hence wont we touched when we use 3 as the pivot.
for idx in range(unclassified, len(nums)):
if nums[idx] < pivot:
nums[idx], nums[unclassified] = nums[unclassified], nums[idx]
unclassified += 1
时间复杂度 = O(N)，由于有4个不同的元素，因此它将是3次遍历的解决方案。