Я пытаюсь решить проблему, когда мне нужно определить количество пар в массиве, которые имеют то же среднее/среднее значение, что и исходный массив.
Хотя я решил проблему с вложенными циклами (см. код ниже), я хотел уменьшить сложность своего решения, и пока у меня нет никаких идей.
Обновление: «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;
}
Прежде чем вы попытаетесь уменьшить алгоритмическую сложность вашего решения, было бы разумно потратить минуту, чтобы выяснить, какова алгоритмическая сложность вашего решения является. Кроме того, в подобных задачах, если вы начинаете с несортированного массива, вы должны рассмотреть сортируя его в качестве первого шага (O(nlogn)), просто чтобы посмотреть, поможет ли это.
Ожидать, что числа с плавающей запятой будут сравниваться равными, всегда плохая идея из-за небольших ошибок округления. Вместо этого вы должны перекрестно умножать. sum(Arr) * 2 == (Arr[j] + Arr[k]) * N
- это правильный способ проверить, что пара имеет то же среднее значение, что и массив (используя только целочисленную математику).
Вы также должны быть осторожны, чтобы избежать целочисленного переполнения при вычислении суммы массива. Возможно, вам придется использовать 64-битную математику, в зависимости от входных ограничений.
Прежде всего, я хотел бы поблагодарить всех вас за ваши предложения. Я рассмотрю их и соответствующим образом обновлю свой код.
@Beta, я думаю, твое предложение имеет большой смысл. В данный момент у меня нет доступа к моей системе, но я просто подумал о том, что вы написали, и я считаю, что у меня есть решение, которое значительно сократит количество итераций. Я попробую это и вернусь, если это сработало.
@user3386109 user3386109 Я изменил код в исходном сообщении. Внесены следующие изменения: 1. Проверка того, имеет ли пара то же среднее значение, что и массив, с помощью целочисленной математики. 2. Использована функция быстрой сортировки в библиотеке C stdlib.h, чтобы сначала отсортировать массив в порядке возрастания. Затем я запустил второй цикл в порядке убывания от k = N - 1 до j+1 и прервал второй цикл, если среднее значение пары опустилось ниже среднего значения массива. Как вы думаете, это можно сделать без вложенных циклов? Кроме того, приветствуются любые другие предложения по улучшению кода.
Да, это можно сделать и без вложенных циклов, но часть работы придется сделать самому. Попробуйте карандашом и бумагой.
{ 1, 4, 5, ... , 15, 18, 21 }
, с N элементами, а сумма элементов равна 8N. Первая пара для проверки — это первый и последний элементы массива 8N * 2 == (1 + 21) * N
, которые не совпадают, потому что 16 < 22
. Какую следующую пару вы собираетесь проверить?
@ user3386109 Я рад, что меня здесь не кормят с ложечки. Итак, если вы видите обновленный код, программа теперь делает и будет делать в приведенном выше случае, она будет проверять, если 8N * 2 == (1 + 21) * N. Поскольку это не так, и среднее значение 2 номеров > среднее значение массива, программа должна продолжить проверку. Теперь он (и ответ на ваш вопрос) проверит пару 1 и 18. Он будет продолжать выполнять те же проверки до тех пор, пока среднее значение пары не сравняется со средним значением массива (1 и 15 в приведенном выше случае) или меньше, чем это . Если меньше, прекращаем проверку с 1 и переходим к 4.
Извините, это моя ошибка. Я пропустил модификацию петель. Я ожидал увидеть одну петлю, а когда их было еще две, не стал присматриваться. Похоже, что эти петли могут работать. Следующим шагом будет обработка массива с дубликатами. Например, если массив содержит {1, 1, 1,..., 15, 15}, то они считаются как 6 пар. Дубликаты проще (imo), если есть только один цикл. Я опубликовал ответ, демонстрирующий решение с одним циклом.
Общий подход к подобным проблемам заключается в использовании одного цикла, поддерживающего два индекса. Один индекс начинается в начале массива, другой — в конце. Когда индексы встречаются посередине, цикл завершается. В теле цикла код должен решить, обновлять ли один индекс, другой или оба.
Для этой конкретной проблемы есть пара дополнительных недостатков, вызванных дубликатами в массиве.
Например, для массива { 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
Вам нужно среднее значение для всех N, прежде чем вы начнете цикл, чтобы найти пары, которые ему соответствуют. Итак, 2 отдельных, пока или не все вложены вместе.