Уникальные пары с равной суммой в C

Question

Вопрос под рукой:

Q8. Задан несортированный массив A [].Задача состоит в том, чтобы напечатать все уникальные пары в несортированном массиве с равной суммой.Рассмотрим входные данные: A [] = {6, 4, 12, 10, 22, 54, 32, 42, 21, 11}
Объясните подход решения вышеуказанной проблемы и напишите код на любом одном языке программированияC / C ++ / Python / Java.Какова временная сложность вышеупомянутой проблемы?

Вот мое решение вышеуказанной проблемы (в C):

#include <stdio.h>
int main(){
    int arr[]={6,4,12,10,22,54,32,42,21,11};
    int len=sizeof(arr)/sizeof(arr[0]);
    for(int i=0;i<len;i++)
        for(int j=i+1;j<len;j++)
            for(int k=i+1;k<len;k++)
                for(int l=k+1;l<len;l++)
                    if(arr[i]+arr[j]==arr[l]+arr[k])
                        printf("(%d,%d),(%d,%d)\n",arr[i],arr[j],arr[k],arr[l]);
    return 0;
}

Моя логика состоит в том, чтобы брать по одному элементу за раз, ивозьмите его сумму с каждым другим элементом и для каждой такой итерации сравните сумму двух других уникальных пар элементов с ним.Например, когда i = 0, j = 3, arr [i] + arr [j] = 16.Когда k = 1, l = 2, arr [k] + arr [l] = 16.Поскольку пары уникальны (6,10) и (4,12) и их сумма равна, я их печатаю.Обратите внимание, что пары предполагаются как неупорядоченные пары, так что (a, b) совпадает с (b, a), и поэтому нам не нужно повторять это, поскольку они должны быть уникальными.

Мой вопрос: я знаю, что мой код почти O (n ^ 4).Как я могу улучшить / оптимизировать это дальше?

Answer 1

Это будет проще в C ++, Python или Java, потому что эти языки предоставляют контейнеры высокого уровня.В Python вы можете использовать defaultdict(list), где ключом будет сумма, а значением - список пар, дающих эту сумму.

Тогда вам нужно только обработать уникальные пары (N ² / 2)

result = collections.defaultdict(list)
for i, a in enumerate(A):
    for b in A[i+1:]:
        result[a+b].append((a,b))

Это будет немного сложнее в C, потому что у вас нет высокоуровневого прямого доступа.Если вы можете тратить немного памяти и иметь только маленькие числа, как здесь, вы можете сказать, что наибольшая сумма будет меньше, чем в два раза больше самого большого числа во входном массиве, и напрямую выделить массив этого размера.Таким образом, вы гарантируете прямой доступ от суммы.Оттуда вы просто используете связанный список пар, и это все.В качестве бонуса вы даже получаете отсортированный список сумм.

Я не могу предположить, что числа маленькие, вам придется построить контейнер прямого доступа.Контейнера хеш-типа, использующего N * N / 2 в качестве размера (N - это длина A), и суммы% размера в качестве хеш-функции должно быть достаточно.

Для полноты, здесь приведен возможный код C, не выполняющий малыйдопущение чисел (этот код отображает все пары, а не только пары с дублированными суммами):

#include <stdio.h>
#include <stdlib.h>

// a node in a linked list of pairs
struct pair_node {
    int first;
    int second;
    struct pair_node *next;
};

// a slot for a hash type containers of pairs indexed by their sum
struct slot {
    int number;
    struct pair_node *nodes;
    struct slot *next;
};

// utility function to find (or create) a slot for a sum
struct slot* find_slot(struct slot **slots, int size, int sum) {
    struct slot *slt = slots[sum%size];
    while (slt != NULL) {
        if (slt->number == sum) {
            return slt;
        }
        slt = slt->next;
    }
    slt = malloc(sizeof(struct slot));
    slt->number = sum;
    slt->nodes = NULL;
    slt->next = slots[sum%size];
    slots[sum%size] = slt;
    return slt;
}

int main() {
    int A[] = {6,4,12,10,22,54,32,42,21,11};  // the array of numbers
    int N = sizeof(A) / sizeof(A[0]);

    int arr_size = N * N / 2;   // size of the hash table of pairs
    struct slot** result = malloc(arr_size * sizeof(struct slot *));
    for (int i=0; i<arr_size; i++) {
        result[i] = NULL;
    }

    // process unique pairs
    for (int i=0; i<N-1; i++) {
        for (int j=i+1; j<N; j++) {
            int sum = A[i] + A[j];
            // allocate and initialize a node
            struct pair_node *node = malloc(sizeof(*node));
            node->first = A[i];
            node->second = A[j];

            // store the node in the hash container
            struct slot *slt = find_slot(result, arr_size, sum);
            node->next = slt->nodes;
            slt->nodes = node;
        }
    }

    // display the result
    for (int i=0; i<arr_size; i++) {
        for (struct slot* slt=result[i]; slt != NULL;) {
            printf("%d :", slt->number);
            struct pair_node *node = slt->nodes;
            while(node != NULL) {
                printf(" (%d,%d)", node->first, node->second);
                node = node->next;
                free(node);                // free what has been allocated
            }
            printf("\n");
            struct slot *old = slt;
            slt = slt->next;
            free(old);
        }
    }
    free(result);
    return EXIT_SUCCESS;
}

Answer 2

Сначала вы вычисляете сумму каждой пары и сохраняете результат в матрице PAIRSUM.

PAIRSUM(0, 0) = 12
PAIRSUM(0, 1) = 10 a s o

Далее вы перебираете PAIRSUM и видите, где 2 записи похожи.

Таким образом, вы уменьшили большую проблему до меньшей, в которой вы проверяете равенство 2 чисел, а не 2 сумм чисел.

Для этого у вас есть вектор PAIR, в котором по индексу X вы сохраняете записи в PAIRSUM, где сумма была X.

Например, PAIR(10) = { {0, 1} }.

Вы также можете рассмотреть в PAIRSUM только матрицу над диагональю, поэтому для индексов (i,j) есть i>j.

Answer 3

Это можно сделать в O (N ^ 2 * log (N ^ 2) * M), где M - максимальное количество пар (i, j), имеющих одинаковую сумму, поэтому в худшем случае это будет O (N ^ 3 * log (N)).

Позволяет выполнять итерацию для каждой пары 0 <= <strong>i, j

Вам не нужно беспокоиться о следующих парах (i, j), у которых есть сумма, потому что следующие пары при обработке обрабатывают ее.

Answer 4

C-код для расчета всех сумм и хранения сумм с индексами внутри массива структур.Затем мы сортируем структуры и печатаем смежные элементы структуры с одинаковой суммой.

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <errno.h>
#include <assert.h>

// for debugging
#define debug(...)  ((void)0) // printf(__VA_ARGS__)

// two indexes and a sum
struct is_s {
    // one index inside the array
    size_t i;
    // the other index also inside the array
    size_t j;
    // no idea, must be random
    int sum;
};

// used for qsoring the struct is_s
static int is_qsort_compare_sum(const void *a0, const void *b0) {
    const struct is_s * const a = a0;
    const struct is_s * const b = b0;
    return a->sum - b->sum;
}

int unique_pairs(const size_t len, const int arr[len]) {
    if (len <= 1) return 0;
    // The number of unsorted combinations must be n!/(2!*(n-2)!)
    const size_t islen = len * (len - 1) / 2; // @MOehm
    debug("%zu\n", islen);

    struct is_s * const is = malloc(islen * sizeof(*is));
    if (is == NULL) {
        return -ENOMEM;
    }

    size_t isidx = 0;
    for (size_t i = 0; i < len; ++i) {
        for (size_t j = i + 1; j < len; ++j) {
            assert(isidx < islen); // just for safety
            struct is_s * const p = &is[isidx++];
            p->i = i;
            p->j = j;
            p->sum = arr[i] + arr[j];
            debug("[%zu]=[%zu]=%d [%zu]=%d %d\n", isidx, p->i, arr[p->i], p->j, arr[p->j], p->sum);
        }
    }

    qsort(is, islen, sizeof(*is), is_qsort_compare_sum);

    for (size_t i = 0; i < islen - 1; ++i) {
        debug("([%zu]=%d,[%zu]=%d)%d = ([%zu]=%d,[%zu]=%d)%d\n", 
            is[i].i, arr[is[i].i], is[i].j, arr[is[i].j], is[i].sum,
            is[i+1].i, arr[is[i+1].i], is[i+1].j, arr[is[i+1].j], is[i+1].sum
        );
        if (is[i].sum == is[i + 1].sum) {
            printf("(%d,%d),(%d,%d) = %d\n",
                arr[is[i].i], arr[is[i].j],
                arr[is[i+1].i], arr[is[i+1].j], is[i].sum);
        }
    }

    free(is);

    return 0;
}

int main(void) {
    const int arr[] = {6,4,12,10,22,54,32,42,21,11};
    return unique_pairs(sizeof(arr)/sizeof(*arr), arr);
}

Результат, который я получаю:

(6,10),(4,12) = 16
(10,22),(21,11) = 32
(12,21),(22,11) = 33
(22,21),(32,11) = 43
(32,21),(42,11) = 53
(12,42),(22,32) = 54
(10,54),(22,42) = 64

Как мне интересно, если это правильно, как @Bathshebaотметил, я думаю, худший случай O (n * n).