Найдите пары в массиве с тем же средним значением, что и массив

Я пытаюсь решить проблему, когда мне нужно определить количество пар в массиве, которые имеют то же среднее/среднее значение, что и исходный массив.

Хотя я решил проблему с вложенными циклами (см. код ниже), я хотел уменьшить сложность своего решения, и пока у меня нет никаких идей.

Обновление: «T» — это просто переменная, представляющая количество тестовых случаев. Можно предположить, что это 1.

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

int comparator(const void *p, const void *q) {
  int l = *(int *)p;
  int r = *(int *)q;
    return (l-r);
}
    
int fSum(int *Arr, int N){
    int sum = 0;

    for(int i=0; i<N; i++){
        sum+=Arr[i];
        }

    return sum;
}

int main(void) {
    int i=1, T, N, pos = 1, j=0, k=0, c = 0, sum;
    int Arr[100000];
    
    scanf("%d",&T);

    while(i<=T){
     scanf("%d", &N);
     c = 0;
     j = 0;

     while(j<N){
        scanf("%d", &Arr[j]);
        ++j;
     }

     qsort(Arr, N, sizeof(int), comparator);

     sum = fSum(Arr, N);

     for(j=0; j<N-1; j++){
        for(k=N-1; k>=j+1; k--){
           if(sum*2 == ((Arr[j]+Arr[k])*N)) {
                c++;
            }
            else{
                if(sum*2 > ((Arr[j]+Arr[k])*N))
                 break;
            }
        }
     }
       printf("%d\n", c);
     ++i;
    }
    return 0;
}

Вам нужно среднее значение для всех N, прежде чем вы начнете цикл, чтобы найти пары, которые ему соответствуют. Итак, 2 отдельных, пока или не все вложены вместе.

Dave S 23.04.2022 04:01

Прежде чем вы попытаетесь уменьшить алгоритмическую сложность вашего решения, было бы разумно потратить минуту, чтобы выяснить, какова алгоритмическая сложность вашего решения является. Кроме того, в подобных задачах, если вы начинаете с несортированного массива, вы должны рассмотреть сортируя его в качестве первого шага (O(nlogn)), просто чтобы посмотреть, поможет ли это.

Beta 23.04.2022 04:28

Ожидать, что числа с плавающей запятой будут сравниваться равными, всегда плохая идея из-за небольших ошибок округления. Вместо этого вы должны перекрестно умножать. sum(Arr) * 2 == (Arr[j] + Arr[k]) * N - это правильный способ проверить, что пара имеет то же среднее значение, что и массив (используя только целочисленную математику).

user3386109 23.04.2022 04:29

Вы также должны быть осторожны, чтобы избежать целочисленного переполнения при вычислении суммы массива. Возможно, вам придется использовать 64-битную математику, в зависимости от входных ограничений.

user3386109 23.04.2022 04:37

Прежде всего, я хотел бы поблагодарить всех вас за ваши предложения. Я рассмотрю их и соответствующим образом обновлю свой код.

siddharth ghosh 23.04.2022 07:45

@Beta, я думаю, твое предложение имеет большой смысл. В данный момент у меня нет доступа к моей системе, но я просто подумал о том, что вы написали, и я считаю, что у меня есть решение, которое значительно сократит количество итераций. Я попробую это и вернусь, если это сработало.

siddharth ghosh 23.04.2022 07:48

@user3386109 user3386109 Я изменил код в исходном сообщении. Внесены следующие изменения: 1. Проверка того, имеет ли пара то же среднее значение, что и массив, с помощью целочисленной математики. 2. Использована функция быстрой сортировки в библиотеке C stdlib.h, чтобы сначала отсортировать массив в порядке возрастания. Затем я запустил второй цикл в порядке убывания от k = N - 1 до j+1 и прервал второй цикл, если среднее значение пары опустилось ниже среднего значения массива. Как вы думаете, это можно сделать без вложенных циклов? Кроме того, приветствуются любые другие предложения по улучшению кода.

siddharth ghosh 23.04.2022 14:21

Да, это можно сделать и без вложенных циклов, но часть работы придется сделать самому. Попробуйте карандашом и бумагой.

Beta 23.04.2022 15:48
Сократический пример, отсортированный массив { 1, 4, 5, ... , 15, 18, 21 }, с N элементами, а сумма элементов равна 8N. Первая пара для проверки — это первый и последний элементы массива 8N * 2 == (1 + 21) * N, которые не совпадают, потому что 16 < 22. Какую следующую пару вы собираетесь проверить?
user3386109 23.04.2022 21:22

@ user3386109 Я рад, что меня здесь не кормят с ложечки. Итак, если вы видите обновленный код, программа теперь делает и будет делать в приведенном выше случае, она будет проверять, если 8N * 2 == (1 + 21) * N. Поскольку это не так, и среднее значение 2 номеров > среднее значение массива, программа должна продолжить проверку. Теперь он (и ответ на ваш вопрос) проверит пару 1 и 18. Он будет продолжать выполнять те же проверки до тех пор, пока среднее значение пары не сравняется со средним значением массива (1 и 15 в приведенном выше случае) или меньше, чем это . Если меньше, прекращаем проверку с 1 и переходим к 4.

siddharth ghosh 24.04.2022 06:21

Извините, это моя ошибка. Я пропустил модификацию петель. Я ожидал увидеть одну петлю, а когда их было еще две, не стал присматриваться. Похоже, что эти петли могут работать. Следующим шагом будет обработка массива с дубликатами. Например, если массив содержит {1, 1, 1,..., 15, 15}, то они считаются как 6 пар. Дубликаты проще (imo), если есть только один цикл. Я опубликовал ответ, демонстрирующий решение с одним циклом.

user3386109 24.04.2022 08:28
3 метода стилизации элементов HTML
3 метода стилизации элементов HTML
Когда дело доходит до применения какого-либо стиля к нашему HTML, существует три подхода: встроенный, внутренний и внешний. Предпочтительным обычно...
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
3
11
83
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Общий подход к подобным проблемам заключается в использовании одного цикла, поддерживающего два индекса. Один индекс начинается в начале массива, другой — в конце. Когда индексы встречаются посередине, цикл завершается. В теле цикла код должен решить, обновлять ли один индекс, другой или оба.

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

Например, для массива { 1, 1, 1, 4, 5, 12, 15, 15, 18 } имеется 7 пар. Есть три 1, которые могут быть сопоставлены с любой из двух 15, что дает 6 возможных пар. Пара 4,12 — седьмая пара. Поэтому, когда код находит пару различных чисел с правильным средним значением, он должен подсчитать количество дубликатов каждого числа. Затем количество пар обновляется произведением двух подсчетов.

Учитывая массив { 2, 3, 4, 8, 8, 8, 12, 12, 15 }, есть 5 пар. Три пары из-за трех восьмерок плюс два способа спаривания 4 с 12. Когда среднее значение присутствует в массиве и дублируется, один индекс достигнет первого экземпляра среднего, а другой — последнего. . Количество дубликатов можно вычислить по двум индексам, а количество пар — это количество способов выбрать любые два дубликата.

Вот пример реализации с использованием одного цикла, который обновляет два индекса:

#include <stdio.h>

void showArray(int Arr[], int N)
{
    printf("Arr[] = {");
    if (N > 0)
        printf(" %d", Arr[0]);
    for (int i = 1; i < N; i++)
        printf(", %d", Arr[i]);
    printf(" }\n");
}

int computeSum(int Arr[], int N)
{
    int sum = 0;
    for (int i=0; i < N; i++)
        sum += Arr[i];
    return sum;
}

int solve(int Arr[], int N)
{
    showArray(Arr, N);
    int sum = computeSum(Arr, N);
    printf("N=%d sum=%d\n", N, sum);

    int pairs = 0;
    for (int j=0, k=N-1; k > j; )
    {
        if ((Arr[j] + Arr[k])*N > sum*2)
        {
            // the average is too high, so skip the larger value
            k--;
        }
        else if ((Arr[j] + Arr[k])*N < sum*2)
        {
            // the average is too low, so skip the smaller value
            j++;
        }
        else if (Arr[j] == Arr[k])
        {
            // handle the case where the average value is present and duplicated
            int repeat = k - j + 1;
            pairs += (repeat * (repeat-1)) / 2;
            break;
        }
        else
        {
            // handle the case where two distinct numbers in the array have the correct average
            // note that if there are duplicates of the numbers, the indexes are updated to the next non-duplicate
            int oldj = j++;
            while (Arr[j] == Arr[oldj])
                j++;
            int oldk = k--;
            while (Arr[k] == Arr[oldk])
                k--;
            pairs += (j - oldj) * (oldk - k);
        }
    }

    return pairs;
}

#define len(arr) (sizeof(arr) / sizeof(arr[0]))

int main(void)
{
    int Arr1[] = { 1, 4, 5, 6, 6, 7, 7, 11, 15, 18 };
    printf("pairs=%d\n\n", solve(Arr1, len(Arr1)));

    int Arr2[] = { 1, 1, 1, 4, 5, 12, 15, 15, 18 };
    printf("pairs=%d\n\n", solve(Arr2, len(Arr2)));

    int Arr3[] = { 2, 3, 4, 8, 8, 8, 12, 12, 15 };
    printf("pairs=%d\n\n", solve(Arr3, len(Arr3)));
}

Вывод из кода:

Arr[] = { 1, 4, 5, 6, 6, 7, 7, 11, 15, 18 }
N=10 sum=80
pairs=2

Arr[] = { 1, 1, 1, 4, 5, 12, 15, 15, 18 }
N=9 sum=72
pairs=7

Arr[] = { 2, 3, 4, 8, 8, 8, 12, 12, 15 }
N=9 sum=72
pairs=5

Другие вопросы по теме