从对和数组构造一个数组-yiteyi-C++库

给定对和数组和原始数组的大小（n），构造原始数组。数组的pair sum数组是包含所有有序对之和的数组。例如，arr[]={6,8,3,4}的对和数组是{14,9,10,11,12,7}。一般来说，arr[0..n-1]的对和数组是{arr[0]+arr[1]、arr[0]+arr[2]、…、arr[1]+arr[2]、arr[1]+arr[3]、…、arr[2]+arr[4]、…、arr[n-2]+arr[n-1}。给定对和数组，构造原始数组 我们强烈建议您尽量减少浏览器数量，并亲自尝试。 假设给定的数组是“pair[]，并且在原始数组中有n个元素。如果我们看几个例子，我们可以观察到arr[0]是对[0]+对[1]-对[n-1]的一半。请注意，对[0]+对[1]–对[n-1]的值是（arr[0]+对[1]）+（arr[0]+对[2]）–（arr[1]+对[2]）。一旦我们计算了arr[0]，我们就可以通过减去arr[0]来计算其他元素。例如，可以通过从对[0]中减去arr[0]来计算arr[1]，也可以通过从对[1]中减去arr[0]来计算arr[2]。以下是上述理念的实施。

null

C++

                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Fills element in arr[] from its pair sum array pair[].                       
                         // n is size of arr[]                       
                         void                                     constructArr(                                     int                                     arr[],                                     int                                     pair[],                                     int                                     n)                       
                         {                       
                                                 arr[0] = (pair[0]+pair[1]-pair[n-1]) / 2;                       
                                                 for                                     (                                     int                                     i=1; i<n; i++)                       
                                                 arr[i] = pair[i-1]-arr[0];                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     pair[] = {15, 13, 11, 10, 12, 10, 9, 8, 7, 5};                       
                                                 int                                     n = 5;                       
                                                 int                                     arr[n];                       
                                                 constructArr(arr, pair, n);                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         import                                     java.io.*;                       
           
                         class                                     PairSum {                       
                                   
                                                 // Fills element in arr[] from its pair sum array pair[].                       
                                                 // n is size of arr[]                       
                                                 static                                     void                                     constructArr(                                     int                                     arr[],                                     int                                     pair[],                                     int                                     n)                       
                                                 {                       
                                                 arr[                                     0                                     ] = (pair[                                     0                                     ]+pair[                                     1                                     ]-pair[n-                                     1                                     ]) /                                     2                                     ;                       
                                                 for                                     (                                     int                                     i=                                     1                                     ; i<n; i++)                       
                                                 arr[i] = pair[i-                                     1                                     ]-arr[                                     0                                     ];                       
                                                 }                       
                                   
                                                 // Driver program to test above function                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     pair[] = {                                     15                                     ,                                     13                                     ,                                     11                                     ,                                     10                                     ,                                     12                                     ,                                     10                                     ,                                     9                                     ,                                     8                                     ,                                     7                                     ,                                     5                                     };                       
                                                 int                                     n =                                     5                                     ;                       
                                                 int                                     [] arr =                                     new                                     int                                     [n];                       
                                                 constructArr(arr, pair, n);                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 System.out.print(arr[i]+                                     " "                                     );                       
                                                 }                       
                         }                       
                         /* This code is contributed by Devesh Agrawal */                       

Python3

                         # Fills element in arr[] from its                       
                         # pair sum array pair[].                       
                         # n is size of arr[]                       
           
                         def                                     constructArr(arr,pair,n):                       
                                                 arr [                                     0                                     ]                                     =                                     (pair[                                     0                                     ]                                     +                                     pair[                                     1                                     ]                                     -                                     pair[n                                     -                                     1                                     ])                                     /                                     /                                     2                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,n):                       
                                                 arr[i]                                     =                                     pair[i                                     -                                     1                                     ]                                     -                                     arr[                                     0                                     ]                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 pair                                     =                                     [                                     15                                     ,                                     13                                     ,                                     11                                     ,                                     10                                     ,                                     12                                     ,                                     10                                     ,                                     9                                     ,                                     8                                     ,                                     7                                     ,                                     5                                     ]                       
                                                 n                                     =                                     5                       
                                                 arr                                     =                                     [                                     0                                     ]                                     *                                     n                       
                                                 constructArr(arr,pair,n)                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 print                                     (arr[i],end                                     =                                     " "                                     )                       
           
                         # This code is contributed by                       
                         # Shrikant13                       

C#

                         // C# program to construct an                       
                         // array from its pair-sum array                       
                         using                                     System;                       
           
                         class                                     PairSum                       
                         {                       
                                                 // Fills element in arr[] from its                       
                                                 // pair sum array pair[].                       
                                                 // n is size of arr[]                       
                                                 static                                     void                                     constructArr(                                     int                                     []arr,                                     int                                     []pair,                       
                                                 int                                     n)                       
                                                 {                       
                                                 arr[0] = (pair[0] + pair[1] - pair[n - 1]) / 2;                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 arr[i] = pair[i - 1] - arr[0];                       
                                                 }                       
                                   
                                                 // Driver program to test above function                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []pair = {15, 13, 11, 10, 12,                       
                                                 10, 9, 8, 7, 5};                       
                                                 int                                     n = 5;                       
                                                 int                                     []arr =                                     new                                     int                                     [n];                       
                                                 constructArr(arr, pair, n);                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal                       

PHP

                         <?php                       
                         // Fills element in arr[] from                       
                         // its pair sum array pair[].                       
                         // n is size of arr[]                       
                         function                                     constructArr(                                     $pair                                     )                       
                         {                       
                                                 $arr                                     =                                     array                                     ();                       
                                                 $n                                     = 5;                       
                                                 $arr                                     [0] =                                     intval                                     ((                                     $pair                                     [0] +                                     $pair                                     [1] -                       
                                                 $pair                                     [                                     $n                                     - 1]) / 2);                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $arr                                     [                                     $i                                     ] =                                     $pair                                     [                                     $i                                     - 1] -                                     $arr                                     [0];                       
                                   
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 echo                                     $arr                                     [                                     $i                                     ] .                                     " "                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $pair                                     =                                     array                                     (15, 13, 11, 10,                       
                                                 12, 10, 9, 8, 7, 5);                       
                         constructArr(                                     $pair                                     );                       
           
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Fills element in arr[] from                       
                         // its pair sum array pair[].                       
                         // n is size of arr[]                       
                         function                                     constructArr(arr, pair, n)                       
                         {                       
                                                 arr[0] = Math.floor((pair[0]+pair[1]-pair[n-1]) / 2);                       
                                                 for                                     (let i=1; i<n; i++)                       
                                                 arr[i] = pair[i-1]-arr[0];                       
                         }                       
           
                         // Driver program to test above function                       
           
                                                 let pair = [15, 13, 11, 10, 12, 10, 9, 8, 7, 5];                       
                                                 let n = 5;                       
                                                 let arr =                                     new                                     Array(n);                       
                                                 constructArr(arr, pair, n);                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
           
           
                         // This code is contributed by Surbhi Tyagi.                       
           
                         </script>                       

输出：

 8 7 5 3 2

constructArr（）的时间复杂度为O（n），其中n是arr[]中的元素数。本文由阿披实撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章