0

每个排序算法都将是工作，但它是一个过度杀伤。

对于像这样的输入：

aa
cc
aa
bb
dd
bb
cc

我只需要类似的东西：

aa
aa
cc
cc
bb
bb
dd

每个模式的顺序不是必需的。

这种工作有这样的算法吗？

4

2 回答 2

6

您只想在这里使用哈希表，或者更抽象地说是关联数组。遍历输入，如果尚未看到它，则将其添加到值为1的哈希表（标记，如果您愿意），或者如果它已经存在于哈希表中，则将计数加一。

因此，该算法在时间和空间上都是O(n)，这与您合理预期的一样好。我建议阅读一下哈希表，因为它是一种非常有用的数据结构，出现在算法和软件设计的各个地方。

于 2013-01-15T01:31:22.463 回答
2

好吧，在我的脑海中，你可以运行一个计算每个元素存在多少的通道，然后创建一个新数组，并按顺序发布它们。那将是 O(n) 但不是“就地”。

因此：

// Make outputArrayCounter
// While inputArray has elements left:
//   if current element is new, add to outputArrayCounter
//   if current element has been seen before, increment a counter associated with that 
//   element.
// Part 2...
// Make outputArray
// create the appropriate number of elements as found in the outputArrayCounter for
// every different element type.

让我们尝试一个例子：

我们有一个原始输入aa bb aa cc cc dd cc。

我们将制作我们的计数器设备，并扫描输入。 aa，第一个元素被读取，因为我们以前从未遇到aa过，我们将把它添加到我们的计数器设备中。

计数器装置：[(aa, 1)]

现在让我们继续阅读下一个输入，bb. 它也没有找到并被添加：

计数器装置：[(aa, 1), (bb, 1)]

再一步并aa作为第三个元素阅读。这可以在我们的设备中找到，因此我们没有再次添加它，而是将关联的计数器增加aa1。

计数器装置：[(aa, 2), (bb, 1)]

我将继续为您提供终端计数器设备状态：

[(aa, 2), (bb, 1), (cc, 3), (dd, 1)]

现在我们遍历设备并多次打印出每个元素的数量，并将每个同名元素放在一起。（如果顺序很重要，这是一个实现细节，它将确定是使用关联的集合字典，还是使用某种存储顺序的双数组设备。这是特定于语言的，但我相信你可以弄清楚。如果你不能，在这里发表评论，我将描述一个解决方案。）

print aa aa bb cc cc cc dd

于 2013-01-15T01:25:12.727 回答