重新排列数组，以便按相同元素分组

Question

我正在处理数组问题，可以通过排序轻松解决。但是，我的要求实际上比完整的要求更宽松：我只需要保证，如果数组中有任何相同的元素，它们在数组中会彼此相邻。

是否有一种算法可以对数组进行重新排序，使其满足上述条件，比仅进行完整排序会更有效？

Answer 1

所以答案是否定的。这些信息并没有真正的帮助。它可以使您好一些，但不能让您大吃一惊。

对于建议使用散列以获得线性时间的每个人，您也可以执行相同的排序。此方法称为基数/哈希排序。它会消耗您的内存。

当有更多限制时，您甚至可以使用更酷的技巧（例如，总和，异或等）。

但是，对于仅在广义数组上使用比较的算法，通过这种方式减少问题并不会带来太大的花费。

为了对此提供一个简单的直觉，假设每个元素有1个冗余，因此您的数组为a1，a1，… an，an（n个唯一数字的2n个元素的总数）。

解决方案空间的大小为n！（只要aj-aj是配对的，您就可以按照问题说明中的指定随时对配对进行置换）。输入空间的大小为（2n）！/（2 ^（n））。

这意味着您的算法需要产生足够的信息来排列（（2n）！/ n！）/（2 ^ n）=（n （n + 1） … 2n）/（2 ^
n）个元素。每次比较都会为您提供1位信息。所需的比较迭代次数为log（n）+ log（n + 1）… +
log（2n）-n，即big_omega（nlog（n））。这并不比排序更好或更糟。

这是排序的半严格处理方法：http
:
//www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf

我可能会受贿为当前问题生成类似的证明。