Ако обхватът им е ограничен (да речем между -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. Това е така, защото стойност 5 с брой 1 всъщност не дава сбор на 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(n2). Причината, поради която двоичното търсене е 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)
person
paxdiablo
schedule
03.11.2009
