خوارزمية قائمة الارتباط للعثور على أزواج تضيف ما يصل إلى 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. وهذا لأن القيمة 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) لأنني لا فرز في هذا الإصدار، فقط باستخدام القيم ك Findes.

إذا كان الحد الأدنى أقل من الصفر (أو مرتفعا جدا إلى النقطة التي سيضيع فيها الكثير من الذاكرة)، فيمكنك فقط استخدام Minval لضبط الفهارس (فحص O (N) آخر للعثور على الحد الأدنى للقيمة ثم استخدمه i-minVal بدلا من i لمؤشرات الصفيف).

وحتى إذا كانت النطاق من المنخفضة إلى الأعلى مكلفة للغاية على الذاكرة، فيمكنك استخدام صفيف متناثر. سيكون عليك فرزها، O (N Log N)، والبحث فيه عن تحديث التهم، وكذلك O (N Log n)، ولكن هذا لا يزال أفضل من الأصل O (N²). السبب في البحث الثنائي هو O (N 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)

Answer 2

قم بإنشاء مجموعة تجزئة (Hashset in Java) (هل يمكن استخدام مجموعة متناثرة إذا كانت الأرقام تحدها جيدا، أي تعلم أنها تقع في +/- 100)

لكل عقدة، تحقق أولا إذا كان 10-n في المجموعة. إذا كان الأمر كذلك، فقد وجدت زوجا. في كلتا الحالتين، ثم أضف N إلى المجموعة واستمر.

لذلك على سبيل المثال لديك 1 - 6 - 3 - 4 - 9

1 - هل 9 في المجموعة؟ لا

6 - 4؟ رقم.

3 - 7؟ رقم.

4 - 6؟ نعم! طباعة (6،4)

9 - 1؟ نعم! طباعة (9،1)

Answer 3

هذه مشكلة Summet Summet مصغرة، والتي هي NP كاملة.

Answer 4

إذا كنت قد قمت أولا بفرز المجموعة، فسيؤدي ذلك إلى القضاء على أزواج الأرقام التي تحتاج إلى تقييمها.