链接列表算法找到最多可达10个

本文介绍了链接列表算法找到最多可达10个的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 你可以建议一个算法，找到链接列表中的所有节点对，最多加起来10. 我想出了以下几点。我认为这个算法应该是有效的，但它肯定不是O（n2）复杂度最高的。任何人都可以提示更有效率的解决方案（可能需要线性时间）。 解决方案如果范围有限（例如介于-100和100之间） ，这很容易。 创建一个数组 quant [-100..100] 然后循环浏览你的链表执行： quant [value] = quant [value] + 1 / pre> 然后，以下循环将会做到这一点。 对于i = -100到100：j = 10 - i for k = 1 to quant [i] * quant [j] output i，，j 即使他们的范围不受限制，您可以使用比您提出的更有效的方法，通过先排序值然后只保留计数而不是单个值（与上述解决方案相同）。 这是通过运行两个指针来实现的，一个在列表的开头，一个在结束。当这些指针的数字加起来为10时，输出它们并将结束指针向下移动，开始指针向上。 当它们大于10时，移动结束指针下降。当它们较少时，将起始指针向上移动。 这取决于排序的性质。小于10意味着你需要使总和更高（向上移动开始指针）。大于10意味着您需要减少总和（结束指针向下）。因为它们在列表中没有重复（因为计数），等于10表示你移动两个指针。 当指针相互通过时停止。 还有一个棘手的位，那就是指针相等，值总和为10（这只能在值为5时发生）。 > 您不输出基于产品的数量，而是基于值减1的乘积。这是因为值为5的值5不为实际上总和为10（因为只有一个5）。 所以，对于列表： 2 3 1 3 5 7 10 -1 11 你得到： / p> 索引abcdefgh 值-1 1 2 3 5 7 10 11 计数1 1 1 2 1 1 1 1 您开始指针 p1 在 a 和 p2 在 h 。由于 -1 + 11 = 10 ，您输出这两个数字（如上所述，您可以执行 N code> N 是计数的产物）。这是一个（ - 1,11）的副本。然后，您将 p1 移动到 b 和 p2 至 g 。 1 + 10> 10 所以离开 p1 在 b ，移动 p2 直到 f 。 1 + 7 所以移动 p1 到 c ，离开 p2 在 f 。 2 + 7 所以移动 p1 到 d ，离开 p2 在 f 。 3 + 7 = 10 由于 d 的数目为2，所以输出两个副本（3,7），移动 p1 to e ， p2 to e 。 5 + 5 = 10 但 p1 = p2 ，所以产品是0或0或0.输出没有，将 p1 移动到 f ， p2 至 d 。 循环结束自 p1> p2 。 因此，总体输出为： $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ pre> 这是正确的。 这是一些测试代码。你会注意到，我已经迫使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]; //生成一些随机数据。 srand（time（0））; （i = 0; i< SZSRC; i ++） { srcData [i] = rand（）％SZSORTED; printf（srcData [％2d] =％5d\\\，i，srcData [i]）; } //转换为值/大小数组。 （i = 0; i< SZSORTED; i ++） { sortedVal [i] = i; sortedCnt [i] = 0; } for（i = 0; i< SZSRC; i ++） sortedCnt [srcData [i]] ++; //强制7 + 7到具体的计数进行测试。 sortedCnt [7] = 2; （i = 0; i< SZSORTED; i ++）如果（sortedCnt [i]！= 0） printf（Sorted [％3d]，count =％3d\ n，i，sortedCnt [i]）; //开始和结束指针。 s = 0; e = SZSORTED - 1; //循环直到它们重叠。 while（s //等于所需值？ if（sortedVal [s] + sortedVal [e] == SUM）{ //获取产品（在中点注意特殊情况）。 prod =（s == e）？ （sortedCnt [s] - 1）*（sortedCnt [e] - 1）：sortedCnt [s] * sortedCnt [e]; //输出正确的计数。 （i = 0; i< prod; i ++） printf（（％3d，％3d）\\\，sortedVal [s]，sortedVal [e]） ; //移动两个指针并继续。 s ++; e--; 继续; } //不满意，移动开始指针。 if（sortedVal [s] + sortedVal [e]< SUM）{ s ++; 继续; } //大于期望，移动结束指针。 e--; } return 0; } 你会看到上面的代码都是O（n），因为我'在这个版本中没有排序，只是智能地使用这些值作为索引。 如果最小值低于零（或非常高，那么浪费太多内存），您可以使用minVal来调整索引（另一个O（n）扫描以找到最小值，然后使用 i-minVal 而不是 i 用于数组索引）。 而且，即使从低到高的范围内存太贵，可以使用一个稀疏的数组。您将不得不对O（n log n）进行排序，并搜索更新计数，也是O（n log n），但仍比原始O（n 2 ）更好。二进制搜索是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 排序[0]，count = 1 排序[3]，count = 3 排序[5]，count = 2 排序[7]，count = 2 排序[8]，count = 3 排序[9]，count = 5 排序[10]，count = 1 So [11]，count = 1 排序[12]，count = 2 排序[13]，count = 3 排序[14]，count = 2 排序[ 16]，count = 4 排序[17]，count = 1 排序[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） Can you suggest an algorithm that find all pairs of nodes in a link list that add up to 10.I came up with the following.I think this algorithm should work however its certainly not the most efficient one having a complexity of O(n2). Can anyone hint at a solution which is more efficient (perhaps takes linear time). Additional or temporary nodes can be used by such a solution. 解决方案 If their range is limited (say between -100 and 100), it's easy.Create an array quant[-100..100] then just cycle through your linked list, executing:quant[value] = quant[value] + 1Then the following loop will do the trick.for i = -100 to 100: j = 10 - i for k = 1 to quant[i] * quant[j] output i, " ", jEven if their range isn't limited, you can have a more efficient method than what you proposed, by sorting the values first and then just keeping counts rather than individual values (same as the above solution).This is achieved by running two pointers, one at the start of the list and one at the end. When the numbers at those pointers add up to 10, output them and move the end pointer down and the start pointer up.When they're greater than 10, move the end pointer down. When they're less, move the start pointer up.This relies on the sorted nature. Less than 10 means you need to make the sum higher (move start pointer up). Greater than 10 means you need to make the sum less (end pointer down). Since they're are no duplicates in the list (because of the counts), being equal to 10 means you move both pointers.Stop when the pointers pass each other.There's one more tricky bit and that's when the pointers are equal and the value sums to 10 (this can only happen when the value is 5, obviously).You don't output the number of pairs based on the product, rather it's based on the product of the value minus 1. That's because a value 5 with count of 1 doesn't actually sum to 10 (since there's only one 5).So, for the list:2 3 1 3 5 7 10 -1 11you get:Index a b c d e f g hValue -1 1 2 3 5 7 10 11Count 1 1 1 2 1 1 1 1You start pointer p1 at a and p2 at h. Since -1 + 11 = 10, you output those two numbers (as above, you do it N times where N is the product of the counts). Thats one copy of (-1,11). Then you move p1 to b and p2 to g.1 + 10 > 10 so leave p1 at b, move p2 down to f.1 + 7 < 10 so move p1 to c, leave p2 at f.2 + 7 < 10 so move p1 to d, leave p2 at f.3 + 7 = 10, output two copies of (3,7) since the count of d is 2, move p1 to e, p2 to e.5 + 5 = 10 but p1 = p2 so the product is 0 times 0 or 0. Output nothing, move p1 to f, p2 to d.Loop ends since p1 > p2.Hence the overall output was:(-1,11)( 3, 7)( 3, 7)which is correct.Here's some test code. You'll notice that I've forced 7 (the midpoint) to a specific value for testing. Obviously, you wouldn't do this.#include <stdio.h>#define SZSRC 30#define SZSORTED 20#define SUM 14int 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;}You'll see that the code above is all O(n) since I'm not sorting in this version, just intelligently using the values as indexes.If the minimum is below zero (or very high to the point where it would waste too much memory), you can just use a minVal to adjust the indexes (another O(n) scan to find the minimum value and then just use i-minVal instead of i for array indexes).And, even if the range from low to high is too expensive on memory, you can use a sparse array. You'll have to sort it, O(n log n), and search it for updating counts, also O(n log n), but that's still better than the original O(n2). The reason the binary search is O(n log n) is because a single search would be O(log n) but you have to do it for each value.And here's the output from a test run, which shows you the various stages of calculation. srcData[ 0] = 13srcData[ 1] = 16srcData[ 2] = 9srcData[ 3] = 14srcData[ 4] = 0srcData[ 5] = 8srcData[ 6] = 9srcData[ 7] = 8srcData[ 8] = 5srcData[ 9] = 9srcData[10] = 12srcData[11] = 18srcData[12] = 3srcData[13] = 14srcData[14] = 7srcData[15] = 16srcData[16] = 12srcData[17] = 8srcData[18] = 17srcData[19] = 11srcData[20] = 13srcData[21] = 3srcData[22] = 16srcData[23] = 9srcData[24] = 10srcData[25] = 3srcData[26] = 16srcData[27] = 9srcData[28] = 13srcData[29] = 5Sorted [ 0], count = 1Sorted [ 3], count = 3Sorted [ 5], count = 2Sorted [ 7], count = 2Sorted [ 8], count = 3Sorted [ 9], count = 5Sorted [ 10], count = 1Sorted [ 11], count = 1Sorted [ 12], count = 2Sorted [ 13], count = 3Sorted [ 14], count = 2Sorted [ 16], count = 4Sorted [ 17], count = 1Sorted [ 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) 这篇关于链接列表算法找到最多可达10个的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！