c++ - 在 O(1) 空间和 O(n) 时间的数组中将相同类型的元素组合在一起

Question

这是 Elements of programming interviews 书中的一道题。
问题:

Given an array of n objects with keys that takes on of four values, reorder the array so that the objects that have the same type appear together. Use O(1) additional space and O(n) time.

我无法为超过三个组(荷兰国旗问题)构思一个想法。非常感谢任何帮助。

例如a[6]={1,2,3,4,3,1};那么结果应该是 {1,1,2,3,3,4} 或任何顺序，只有数字的分组很重要(即结果不需要按升序排列)

Answer 1

为了使具有相同颜色的标志聚集在一起，我们可以有一个指针变量并将所有具有当前标志的元素交换到左侧，并对每个后续标志重复此操作。最后，我们会将所有 4 个标志组合在一起。空间复杂度为 O(1)，时间复杂度为 O(标志数 * n)。由于您案例的标志是 4，因此它将是 O(4 * n) = O(n)。

#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)。