在数组中查找与数组具有相同均值的对

Question

我正在尝试解决一个问题，我必须确定数组中与原始数组具有相同 mean/average 的对数。

虽然我已经解决了嵌套循环的问题（参考下面的代码），但我想降低解决方案的复杂性，目前我还没有任何想法。

更新：'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;
}

Answer 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对。由于三个 8 而形成三对，加上将 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

在数组中查找与数组具有相同均值的对

Find Pairs in Array with same mean as the Array

arrays

c

average

complexity-theory