data-structures - 链接列表算法查找加起来为 10 的对

Question

您能否建议一种算法，在链接列表中找到所有节点对，加起来为 10。我想出了以下内容。

算法：比较每个节点，从第二个节点开始，每个节点从头节点开始直到前一个节点（在被比较的当前节点之前）并报告所有这样的对。

我认为这个算法应该可以工作，但它肯定不是复杂度为 O(n2) 的最有效的算法。

任何人都可以暗示一个更有效的解决方案（可能需要线性时间）。这种解决方案可以使用附加或临时节点。

score 6 · Accepted Answer

如果它们的范围是有限的（比如在 -100 到 100 之间），这很容易。

创建一个数组quant[-100..100]，然后循环遍历您的链表，执行：

quant[value] = quant[value] + 1

然后下面的循环就可以了。

for i = -100 to 100:
    j = 10 - i
        for k = 1 to quant[i] * quant[j]
            output i, " ", j

即使它们的范围不受限制，您也可以采用比您建议的方法更有效的方法，首先对值进行排序，然后只保留计数而不是单个值（与上述解决方案相同）。

这是通过运行两个指针来实现的，一个在列表的开头，一个在列表的末尾。当这些指针处的数字加起来为 10 时，输出它们并将结束指针向下移动，将开始指针向上移动。

当它们大于 10 时，向下移动结束指针。当它们更少时，将开始指针向上移动。

这依赖于排序的性质。小于 10 意味着您需要使总和更高（向上移动开始指针）。大于 10 意味着您需要减少总和（结束指针向下）。由于它们在列表中没有重复项（因为计数），因此等于 10 意味着您移动了两个指针。

当指针相互通过时停止。

还有一个棘手的问题，那就是当指针相等且值总和为 10 时（显然，这只发生在值为 5 时）。

您不输出基于乘积的对数，而是基于值减 1 的乘积。这是因为计数为 1 的值 5 实际上并不等于 10（因为只有一个 5）。

因此，对于列表：

2 3 1 3 5 7 10 -1 11

你得到：

Index    a  b  c  d  e  f  g  h
Value   -1  1  2  3  5  7 10 11
Count    1  1  1  2  1  1  1  1

p1您在a和p2处开始指针h。由于-1 + 11 = 10，您输出这两个数字（如上所述，您将其N乘以N计数的乘积）。那是一份(-1,11)。然后你移动p1到b和p2到g。
1 + 10 > 10所以离开p1在b，p2向下移动到f。
1 + 7 < 10所以p1搬到，c离开p2。f
2 + 7 < 10所以p1搬到，d离开p2。f
3 + 7 = 10，输出两个副本，(3,7)因为计数d为 2，移动p1到e，p2到e。
5 + 5 = 10 但 p1 = p2因此乘积是 0 乘以 0 或 0。什么都不输出，p1移至f，p2移至d。
循环自p1 > p2.

因此，总体输出为：

(-1,11)
( 3, 7)
( 3, 7)

哪个是对的。

这是一些测试代码。您会注意到我已将 7（中点）强制设置为特定值以进行测试。显然，你不会这样做。

#include <stdio.h>

#define SZSRC 30
#define SZSORTED 20
#define SUM 14

int main (void) {
    int i, s, e, prod;
    int srcData[SZSRC];
    int sortedVal[SZSORTED];
    int sortedCnt[SZSORTED];

    // Make some random data.

    srand (time (0));
    for (i = 0; i < SZSRC; i++) {
        srcData[i] = rand() % SZSORTED;
        printf ("srcData[%2d] = %5d\n", i, srcData[i]);
    }

    // Convert to value/size array.

    for (i = 0; i < SZSORTED; i++) {
        sortedVal[i] = i;
        sortedCnt[i] = 0;
    }
    for (i = 0; i < SZSRC; i++)
        sortedCnt[srcData[i]]++;

    // Force 7+7 to specific count for testing.

    sortedCnt[7] = 2;
    for (i = 0; i < SZSORTED; i++)
        if (sortedCnt[i] != 0)
            printf ("Sorted [%3d], count = %3d\n", i, sortedCnt[i]);

    // Start and end pointers.

    s = 0;
    e = SZSORTED - 1;

    // Loop until they overlap.

    while (s <= e) {
        // Equal to desired value?

        if (sortedVal[s] + sortedVal[e] == SUM) {
            // Get product (note special case at midpoint).

            prod = (s == e)
                ? (sortedCnt[s] - 1) * (sortedCnt[e] - 1)
                : sortedCnt[s] * sortedCnt[e];

            // Output the right count.

            for (i = 0; i < prod; i++)
                printf ("(%3d,%3d)\n", sortedVal[s], sortedVal[e]);

            // Move both pointers and continue.

            s++;
            e--;
            continue;
        }

        // Less than desired, move start pointer.

        if (sortedVal[s] + sortedVal[e] < SUM) {
            s++;
            continue;
        }

        // Greater than desired, move end pointer.

        e--;
    }

    return 0;
}

你会看到上面的代码都是 O(n)，因为我没有在这个版本中排序，只是智能地使用值作为索引。

如果最小值低于零（或非常高以至于会浪费太多内存），您可以只使用 minVal 来调整索引（另一个 O(n) 扫描以找到最小值，然后只使用i-minVal而不是i用于数组索引）。

而且，即使从低到高的范围在内存上过于昂贵，您也可以使用稀疏数组。你必须对它进行排序，O(n log n)，并搜索更新计数，也是 O(n log n)，但这仍然比原来的 O(n ² ) 好。二进制搜索是 O(n log n) 的原因是因为单个搜索将是 O(log n) 但您必须为每个值执行此操作。

这是测试运行的输出，它向您展示了计算的各个阶段。

srcData[ 0] =    13
srcData[ 1] =    16
srcData[ 2] =     9
srcData[ 3] =    14
srcData[ 4] =     0
srcData[ 5] =     8
srcData[ 6] =     9
srcData[ 7] =     8
srcData[ 8] =     5
srcData[ 9] =     9
srcData[10] =    12
srcData[11] =    18
srcData[12] =     3
srcData[13] =    14
srcData[14] =     7
srcData[15] =    16
srcData[16] =    12
srcData[17] =     8
srcData[18] =    17
srcData[19] =    11
srcData[20] =    13
srcData[21] =     3
srcData[22] =    16
srcData[23] =     9
srcData[24] =    10
srcData[25] =     3
srcData[26] =    16
srcData[27] =     9
srcData[28] =    13
srcData[29] =     5
Sorted [  0], count =   1
Sorted [  3], count =   3
Sorted [  5], count =   2
Sorted [  7], count =   2
Sorted [  8], count =   3
Sorted [  9], count =   5
Sorted [ 10], count =   1
Sorted [ 11], count =   1
Sorted [ 12], count =   2
Sorted [ 13], count =   3
Sorted [ 14], count =   2
Sorted [ 16], count =   4
Sorted [ 17], count =   1
Sorted [ 18], count =   1
(  0, 14)
(  0, 14)
(  3, 11)
(  3, 11)
(  3, 11)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  7,  7)

score 2 · Accepted Answer

创建一个哈希集（Java 中的 HashSet）（如果您的数字有界，可以使用稀疏数组，即您知道它们落入 +/- 100）

对于每个节点，首先检查 10-n 是否在集合中。如果是这样，你已经找到了一对。无论哪种方式，然后将 n 添加到集合中并继续。

所以例如你有 1 - 6 - 3 - 4 - 9

1 - 是 9 在集合中吗？没有

6 - 4？不。

3 - 7？不。

4 - 6？是的！打印 (6,4)

9 - 1？是的！打印 (9,1)

score 1 · Accepted Answer

1

这是一个小子集和问题，它是 NP 完全的。

于 2009-11-03T06:24:40.597 回答

score 0 · Accepted Answer

0

如果您首先对集合进行排序，它将消除需要评估的数字对。

于 2009-11-04T21:41:24.953 回答

data-structures - 链接列表算法查找加起来为 10 的对

4 回答 4

Related

Reference