给定数组中所有对的绝对差之和-yiteyi-C++库

给定一个不同元素的排序数组，任务是求给定数组中所有对的绝对差之和。例如：

null

Input : arr[] = {1, 2, 3, 4}Output: 10Sum of |2-1| + |3-1| + |4-1| +       |3-2| + |4-2| + |4-3| = 10Input : arr[] = {1, 8, 9, 15, 16}Output: 74Input : arr[] = {1, 2, 3, 4, 5, 7, 9, 11, 14}Output: 188

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 简单解决方案 因为这个问题是一个接一个地寻找每一对，把他们的差异总结在一起。这种方法的时间复杂度为O（n） ^2. ). 一 有效解决方案 对于这个问题需要一个简单的观察。由于数组是排序的，当我们取对的绝对差之和时，元素是不同的，所以第i个位置的每个元素加上“i”次，减去“n-1-i”次。例如，在{1,2,3,4}元素中，索引2是arr[2]=3，所以所有以3为一个元素的对将是（1,3），（2,3）和（3,4），现在当我们求对的绝对差之和时，对于所有以3为一个元素的对，求和将是=（3-1）+（3-2）+（4-3）。我们可以看到，3加i=2次，减去n-1-i=（4-1-2）=1次。每个元素的广义表达式为sum=sum+（i*a[i]）–（n-1-i）*a[i]。

C++

                         // C++ program to find sum of absolutre differences                       
                         // in all pairs in a sorted array of distinct numbers                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to calculate sum of absolute difference                       
                         // of all pairs in array                       
                         // arr[]  --> array of elements                       
                         int                                     sumPairs(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // final result                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i=n-1; i>=0; i--)                       
                                                 sum += i*arr[i] - (n-1-i)*arr[i];                       
                                                 return                                     sum;                       
                         }                       
           
                         // Driver program to run the case                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 8, 9, 15, 16};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 cout << sumPairs(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find sum of absolutre                       
                         // differences in all pairs in a sorted                       
                         // array of distinct numbers                       
                         class                                     GFG {                       
                                   
                                                 // Function to calculate sum of absolute                       
                                                 // difference of all pairs in array                       
                                                 // arr[] --> array of elements                       
                                                 static                                     int                                     sumPairs(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                   
                                                 // final result                       
                                                 int                                     sum =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i = n -                                     1                                     ; i >=                                     0                                     ; i--)                       
                                                 sum += i * arr[i] - (n -                                     1                                     - i)                       
                                                 * arr[i];                       
                                   
                                                 return                                     sum;                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     main(String arg[])                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     8                                     ,                                     9                                     ,                                     15                                     ,                                     16                                     };                       
                                                 int                                     n = arr.length;                       
                                   
                                                 System.out.print(sumPairs(arr, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python3 program to find sum of                       
                         # absolutre differences in all pairs                       
                         # in a sorted array of distinct numbers                       
           
                         # Function to calculate sum of absolute                       
                         # difference of all pairs in array                       
                         # arr[] --> array of elements                       
                         def                                     sumPairs(arr, n):                       
           
                                                 # final result                       
                                                 sum                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (n                                     -                                     1                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ):                       
                                                 sum                                     +                                     =                                     i                                     *                                     arr[i]                                     -                                     (n                                     -                                     1                                     -                                     i)                                     *                                     arr[i]                       
                                                 return                                     sum                       
           
                         # Driver program                       
                         arr                                     =                                     [                                     1                                     ,                                     8                                     ,                                     9                                     ,                                     15                                     ,                                     16                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (sumPairs(arr, n))                       
           
                         # This code is contributed by Anant Agarwal.                       

C#

                         // C# program to find sum of absolutre                       
                         // differences in all pairs in a sorted                       
                         // array of distinct numbers                       
                         using                                     System;                       
                         class                                     GFG {                       
                                   
                                                 // Function to calculate sum of absolute                       
                                                 // difference of all pairs in array                       
                                                 // arr[] --> array of elements                       
                                                 static                                     int                                     sumPairs(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                   
                                                 // final result                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = n - 1; i >= 0; i--)                       
                                                 sum += i * arr[i] - (n - 1 - i)                       
                                                 * arr[i];                       
                                   
                                                 return                                     sum;                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr = { 1, 8, 9, 15, 16 };                       
                                                 int                                     n = arr.Length;                       
                                   
                                                 Console.Write(sumPairs(arr, n));                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by nitin mittal.                       

PHP

                         <?php                       
           
                         // PHP program to find sum of absolutre differences                       
                         // in all pairs in a sorted array of distinct numbers                       
           
                         // Function to calculate sum of absolute difference                       
                         // of all pairs in array                       
                         // arr[] --> array of elements                       
                         function                                     sumPairs(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 // final result                       
                                                 $sum                                     = 0;                       
                                                 for                                     (                                     $i                                     =                                     $n                                     -1;                                     $i                                     >=0;                                     $i                                     --)                       
                                                 $sum                                     =                                     $sum                                     +                                     $i                                     *                                     $arr                                     [                                     $i                                     ] - (                                     $n                                     -1-                                     $i                                     )*                                     $arr                                     [                                     $i                                     ];                       
                                                 return                                     $sum                                     ;                       
                         }                       
           
                         // Driver program to run the case                       
                         $arr                                     =                                     array                                     (1, 8, 9, 15, 16);                       
                                                 $n                                     = sizeof(                                     $arr                                     )/sizeof(                                     $arr                                     [0]);                       
                                                 echo                                     sumPairs(                                     $arr                                     ,                                     $n                                     );                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find                       
                         // sum of absolutre differences                       
                         // in all pairs in a sorted array                       
                         // of distinct numbers                       
           
                         // Function to calculate sum of absolute difference                       
                         // of all pairs in array                       
                         // arr[]  --> array of elements                       
                         function                                     sumPairs( arr, n)                       
                         {                       
                                                 // final result                       
                                                 let sum = 0;                       
                                                 for                                     (let i=n-1; i>=0; i--)                       
                                                 sum += i*arr[i] - (n-1-i)*arr[i];                       
                                                 return                                     sum;                       
                         }                       
           
                         // Driver program to run the case                       
                         let arr = [ 1, 8, 9, 15, 16 ];                       
                         let n = arr.length;                       
                         document.write(sumPairs(arr, n));                       
           
                         </script>                       

输出：

时间复杂度：O（n）辅助空间：O（1）e 如果数组没有排序呢？ 对于数组未排序的情况，有效的解决方案也更好。我们可以先在O（n logn）时间内对数组进行排序，然后在O（n）时间内找到所需的值。所以总的时间复杂度是O（n logn），这仍然比O（n）好 ^2. ) 本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章