1

如果给定 n 个字符串及其长度和一个 add(string s1,string s2) 函数，该函数会将字符串 s2 与 s1 连接起来并返回 s3。我们将如何优化将所有这些字符串连接成一个大字符串的成本。

如果没有给出这样的函数，我们可以简单地创建大小为 (n1 + n2 + ...nn) 的输出字符串，并继续向其附加每个字符串的字符。但是，有了这个函数，我们必须遍历输入字符串 s1 以找到它的结尾，然后开始将字符串 s2 连接到它。

所以如果字符串的长度是 2, 6, 1, 3, 4 ..

add (s1, s2) traversal for length 2, op string of length 8
add (s1, s3) traversal for length (2+6) op string of length 9
add (s1, s4) traversal for length (2+6+1) op string of length 12
add (s1, s5) traversal for length (2+6+1+3) op string of length 16...and so on..
4

2 回答 2

1 
"with this function given we'd have to traverse input string s1 
to find it's end and then start concatenating string s2 to it. "

您可以在遍历字符串时逐个字符地连接它。将一个小字符串附加到结果字符串后，您可以获取指向结果字符串末尾的指针。因此，在添加下一个小字符串时，请使用它，这样您就不必再次遍历该位置。

于 2012-10-11T04:59:00.493 回答
0

Thera 有两种方法可以做到这一点。

  1. 对数组进行排序，然后继续连接，这将最大限度地降低成本。

    时间复杂度 O(nlogn) 其中 n 是数组的大小。（假设您使用了快速排序）空间复杂度 O(logn)

  2. 创建数组的最小堆。现在从堆中删除第一个两分钟，添加它们
    并再次添加到堆中，需要多少？

    创建最小堆需要 O(n)。删除第 1 和第 2 分钟将花费 O(n)+O(n)，等待如何？，将 root 替换为最后一个元素并调用 heapify ，它需要 O(logn) ，删除 . 现在我们必须对
    剩余的 n-2 个元素做同样的事情，所以总共需要 O(n-2(logn)) 最糟糕的是，添加两个元素需要 O(1) 并且重新插入并再次调整堆需要 O( logn) 总体而言，它将是 O(nlogn) 的顺序，我们还可以看到在这种情况下需要更多的调用和指令。

总体问题只需要对数组进行排序，我们可以最小化连接的成本，但是如果我们在考虑时间和空间的情况下需要更多地考虑选择正确的排序算法

于 2013-09-05T07:26:59.053 回答