他のすべてのペアの中で値の差が最大のペアの数を見つける方法は？

Question

私は各ペアの間の差を計算し、その要素に関連する最大差異をその場所の同じ配列に格納しました。たとえば、配列は1 2 3ですので、a [0] = 2、a [1] = 1、 1の差が3で最大で2の差が3で最大であるので、配列のサイズを1減らして何の操作をしても、今度は最大の差の値を計算して0番目のインデックスに置きます縮小された配列のサイズまでループを実行し、この最大値が現れる回数を数えますが、このアプローチは時間がかかります。単純なロジックを提案する人もいます。 の入力です。例2の場合はありません。 最初の配列の要素数 1番目の配列のペアの最大数は 2番目の配列の要素はありません 要素の最大数2番目の配列で

#include <stdio.h> 
#include<math.h> 
int max=0; 
int main() 
{ 
    int test_no, n1,n2,i,j,a,b,count1=1,count2=1; 
    scanf("%d",&test_no); 
    printf("\n"); 
    scanf("%d",&n1); 
    printf("\n"); 
    int arr1[n1]; 
    for(i=0;i<n1;i++) 
    { 
     scanf("%d ",&arr1[i]); 
    } 
    for(i=0;i<n1-1;i++) 
    { 
     for(j=i+1;j<=n1-1;j++) 
     { 
      a=abs(arr1[i]-arr1[j]); 
      if(max<=a) 
      max=a; 
     } 
     arr1[i]=max; 
     max=0; 
    } 
    int temp; 
    max=arr1[0]; 
    for(i=1;i<n1-1;i++) 
    { 
     if(max<arr1[i]) 
     { 
      temp=max; 
      max=arr1[i]; 
      arr1[i]=temp; 
      arr1[0]=max; 
     } 
    } 
    for(i=1;i<n1-1;i++) 
    { 
     if(arr1[i]==arr1[0]) 
     { 
      count1++; 
     } 
    } 
    printf("\n"); 
    scanf("%d",&n2); 
    int arr2[n2]; 
    max=0; 
    for(i=0;i<n2;i++) 
    { 
     scanf("%d ",&arr2[i]); 
    } 
    for(i=0;i<n2-1;i++) 
    { 
     for(j=i+1;j<=n2-1;j++) 
     { 
      a=abs(arr2[i]-arr2[j]); 
      if(max<=a) 
      max=a; 
     } 
     arr2[i]=max; 
     max=0; 
    } 
    temp=0; 
    max=arr2[0]; 
    for(i=1;i<n2-1;i++) 
    { 
     if(max<arr2[i]) 
     { 
      temp=max; 
      max=arr2[i]; 
      arr2[i]=temp; 
      arr2[0]=max; 
     } 
    } 
    for(i=1;i<n2-1;i++) 
    { 
     if(arr2[i]==arr2[0]) 
     { 
      count2++; 
     } 
    } 
    printf("%d \n",count1); 
    printf("%d",count2); 
    return 0; 
} 

Answer 1

（これはn log n時間かかる）。

明らかに、最後の要素の値から最初の要素の値を差し引いた値が最大の差です。

同じ違いを取得するために、あなただけ（4言う）最初に等しいどのように多くの要素をカウントする必要があるように、あなたはどのように多くの要素は、同じ第1の要素と同じ終了要素^*を必要とします最後（例えば3）に等しく、2つの値（ここでは3）のうち小さい方を取る。

size_t i; 
for (i = 1; i < arrayLength/2; i++) { 
    if ((sortedArray[i] != sortedArray[0]) 
     || 
     (sortedArray[n-1-i] != sortedArray[n-1])) { 
     break; 
    } 
} 
// i is now the number you need. 

Cで配列をソートするには、既製のライブラリ関数も用意されています。

それとも単にアレイを走査することにより、O（N）時間でこれを行うことができる。

int minVal = INT_MIN; 
int maxVal = INT_MAX; 
int cntMin = 0; 
int cntMax = 0; 
for (i = 0; i < n; i++) { 
    if (arr[i] < minVal) { 
     minVal = arr[i]; 
    } 
    if (arr[i] > maxVal) { 
     maxVal = arr[i]; 
    } 
    if (arr[i] == minVal) { cntMin++; } 
    if (arr[i] == maxVal) { cntMax++; } 
} 
if (minVal == maxVal) { 
    return n/2; 
} 
return min(cntMin, cntMax); 

例：

0 0 0 0 1 2 3 4 5 6 6 6 

最大差は6であり、3回見出されるべきです。

0 1 2 3 4 5 6 6 6 

最大相違はまだ6であり、1回だけ見出されます。

あなたはすべて可能なペア（例えば、[0 、0 、6 、6 、6 ]にあなたがしたい（0 _{をカウントしたい場合あなたのノートはおよそそして、そうでない場合を示しているようだ要素を取り除く代わりに、Tを返す場合でも1}、6 ）...（0 、6 ））、彼はcntMinとcntMaxの最小値を、ちょうど彼らの製品を返します。等しければ、N *（N-1）を返す。二つの異なる番号の同じ差を取得する

^{（*）、それらの一方が矛盾している最初の範囲の、最大値より最小値よりも小さい、またはそれ以上のいずれかでなければならない -}

。例えば。 6と0以外の6を得るには、7と1、または5と-1が必要です。しかし、7は6以上で、-1は0より小さい。配列の最大差は、7または-1のいずれかが含まれていれば、もはや6になりません。

Answer 2

あなたが行う必要があるのは、最大の数がアレイに存在します。あなたがそれをしたら、単純な乗算によってペア数が求められます。

この

は次のように行うことができます。

#include <stdio.h> 
#include <limits.h> 

#define N 7 

int main(void) { 
    int arr[N] = {1, 2, 1, 4, 1, 5, 5}; 
    int max = INT_MIN; 
    int min = INT_MAX; 
    int i; 
    int countmax = 0; 
    int countmin = 0; 

    for (i=0; i < N; ++i) 
    { 
     if (arr[i] > max) 
     { 
      // Found new max value --> reset counter to 1 
      countmax = 1; 
      max = arr[i]; 
     } 
     else if (arr[i] == max) 
     { 
      // Found same max value --> increment counter 
      countmax++; 
     } 
     if (arr[i] < min) 
     { 
      countmin = 1; 
      min = arr[i]; 
     } 
     else if (arr[i] == min) 
     { 
      countmin++; 
     } 
    } 

    if (max == min) 
    { 
     // Special case: All elements are the same 
     printf("%d pairs with difference 0 found\n", N*(N-1)/2); 
    else 
    { 
     printf("%d pairs with difference %d found\n", countmin * countmax, abs(max-min)); 
    } 
    return 0; 
} 

出力：

6 pairs with difference 4 found