5

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

是否有一种算法可以重新排序数组以使其符合上述标准，这比简单地进行完整排序更有效？

4

5 回答 5

6

如果订单不是问题，您可以尝试任何散列技术。所有散列技术通常会导致相似项目的分组。对于数组中的每个项目，只需使用一个哈希函数，所有元素都根据您定义的函数进行分组。

于 2012-12-24T15:32:21.357 回答
3

所以答案是否定的。这些信息并没有真正帮助。它可能会让你好一点，但不是大 O。

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

当有更多限制时，您甚至可以使用更酷的技巧（即求和、异或等）

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

为了给出一个简单的直觉，假设每个元素都有 1 个冗余，所以你的数组是 a1,a1,...an,an（总共 2n 个元素，n 个唯一数字）。

解空间的大小为 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

我可能会被贿赂为当前问题生成类似的证据。

于 2012-12-25T01:52:19.457 回答
1

如果所有元素都可以分成两组，我们可以用哈希解决这个问题。
复杂度是time = O(n)和additional space = O(1)。

如果所有元素都可以分成三组，我们可以应用上述方法两次。
复杂度是time = O(n) * 2 = O(n)和additional space = O(1)。

如果所有元素都可以分成四组，我们可以将第一种方法应用 3 次。
复杂度是time = O(n) * 3 = O(n)和additional space = O(1)。

如果所有元素都可以划分为 k 个组，我们可以应用第一种方法 (k-1) 次。
复杂度是time = O(n) * (k-1) = O(k*n)和additional space = O(k)。

这种方法仅在时间复杂度上优于排序O(k) < O(log n)。

实际上，当所有元素都可以分成三组时，这个问题就变成了Edsger Dijkstra提出的荷兰国旗问题。

于 2012-12-24T19:26:01.843 回答
0

您对不同的键有任何限制吗？

如果没有，您实际上是在寻找哈希袋而不是任何类型的排序。

由于您没有提供任何编程语言，因此这里是一个 python 示例：

from collections import defaultdict

data=[ (1,"a"), (2, "c"), (3, "d"), (2, "b") ]

table = defaultdict(lambda: list())
for key, record in data:
     table[key].append(record)

for key, values in table.iteritems():
    for value in values:
        print key, value

这应该在线性时间内运行，因为哈希表查找被认为是 O(1)。

如果您的数据大于主内存，则经典的外部排序方法可能比严重命中外部哈希表更快。一般来说，全排序会更快，因为算法优化得很好！基准也是如此！

于 2012-12-24T15:57:25.163 回答
0

这个想法类似于上面的 Python 代码，但是在 CL 中：

(defun partition (array &key (test #'eql))
  (loop with table = (make-hash-table :test test)
     for i across array do
       (setf (gethash i table) (1+ (gethash i table 0)))
     finally
       (return
         (loop with result = (make-array (length array))
            with pointer = -1
            for key being the hash-keys of table
            for value being the hash-values of table do
              (loop while (> value 0) do
                   (setf (aref result (incf pointer)) key
                         value (1- value)))
            finally (return result)))))

(partition #(1 2 3 "2" "2" "3" 'a 'b 'b 3 3 1 1 "3" 'a))
;; #(1 1 1 2 3 3 3 "2" "2" "3" 'A 'B 'B "3" 'A)

(partition #(1 2 3 "2" "2" "3" 'a 'b 'b 3 3 1 1 "3" 'a) :test #'equal)
;; #(1 1 1 2 3 3 3 "2" "2" "3" "3" 'A 'A 'B 'B)

它还说明了平等的概念不是既定的。您可以定义您认为什么是相等的，并且根据该定义，将其与排序速度进行比较可能有意义，也可能没有意义（因为排序意味着可以对序列进行排序）。

于 2012-12-24T19:12:34.183 回答