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

Question

你能推荐一种算法来找到链接列表中加起来为 10 的所有节点对吗？ 我想到了以下内容。

Algorithm: Compare each node, starting with the second node, with each node starting from the head node till the previous node (previous to the current node being compared) and report all such pairs.

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

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

Answer 1

如果它们的范围有限(比如在 -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)