链接列表算法查找最多可添加10的对

Question

你能建议一个算法,找到链接列表中所有节点对,加起来就是10.我想出了以下内容.

算法:比较每个节点,从第二个节点开始,每个节点从头节点开始直到前一个节点(比较当前节点之前)并报告所有这些对.

我认为这个算法应该可行,但它当然不是具有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)