元素在1到n范围内时不同元素的总和-yiteyi-C++库

给定一个由n个元素组成的数组，使得数组中的每个元素都是1到n范围内的整数，求该数组中所有不同元素的和。

null

例如：

Input: arr[] = {5, 1, 2, 4, 6, 7, 3, 6, 7}Output: 28The distinct elements in the array are 1, 2, 3, 4, 5, 6, 7Input: arr[] = {1, 1, 1}Output: 1

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

问题已经出现在这里作为一个普遍问题，解决方案也适用于上述情况。但下面将解释一种更好的方法。该方法是通过使这些索引处的元素为负值来标记数组元素的出现。例如，a[0]=1，a[1]=1，a[2]=1。我们检查a[abs（a[i]）-1]是否大于等于0，如果是，则将a[abs（a[i]）-1]标记为负值。i、 e.a[0]=1>=0，我们将a[1-1]标记为[0]=1。接下来，a[1]，检查（abs（a[1]-1）是否为+ve。如果-ve，则表示[1]之前已经出现过，否则这是该元素的第一次出现。请参阅下面的代码。

C++

                         // C++ program to find sum of distinct elements                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         // Returns sum of distinct elements in arr[] assuming                       
                         // that elements in a[] are in range from 1 to n.                       
                         int                                     sumOfDistinct(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                   
                                                 // If element appears first time                       
                                                 if                                     (a[                                     abs                                     (a[i]) - 1] >= 0) {                       
                                                 sum +=                                     abs                                     (a[i]);                       
                                                 a[                                     abs                                     (a[i]) - 1] *= -1;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     sum;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = { 5, 1, 2, 4, 6, 7, 3, 6, 7 };                       
                                                 int                                     n =                                     sizeof                                     (a)/                                     sizeof                                     (a[0]);                       
                                                 cout << sumOfDistinct(a, n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // JAVA program to find sum of distinct                       
                         // elements in sorted order                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
                         import                                     java.math.*;                       
           
                         class                                     GFG{                       
                                   
                                                 // Returns sum of distinct elements in arr[]                       
                                                 // assuming that elements in a[] are in                       
                                                 // range from 1 to n.                       
                                                 static                                     int                                     sumOfDistinct(                                     int                                     a[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     sum =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                   
                                                 // If element appears first time                       
                                                 if                                     (a[Math.abs(a[i]) -                                     1                                     ] >=                                     0                                     ) {                       
                                                 sum += Math.abs(a[i]);                       
                                                 a[Math.abs(a[i]) -                                     1                                     ] *= -                                     1                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     sum;                       
                                                 }                       
           
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     a[] = {                                     5                                     ,                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     6                                     ,                                     7                                     ,                                     3                                     ,                                     6                                     ,                                     7                                     };                       
                                                 int                                     n = a.length;                       
                                                 System.out.println(sumOfDistinct(a, n) );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nikita Tiwari.                       

Python3

                         # Python program to find sum of distinct elements                       
                         # in sorted order                       
                         import                                     math                       
           
                         # Returns sum of distinct elements in arr[]                       
                         # assuming that elements in a[] are in                       
                         # range from 1 to n.                       
                         def                                     sumOfDistinct(a , n) :                       
                                                 sum                                     =                                     0                       
                                                 i                                     =                                     0                       
                                                 while                                     i < n:                       
           
                                                 # If element appears first time                       
                                                 if                                     (a[                                     abs                                     (a[i])                                     -                                     1                                     ] >                                     =                                     0                                     ) :                       
                                                 sum                                     =                                     sum                                     +                                     abs                                     (a[i])                       
                                                 a[                                     abs                                     (a[i])                                     -                                     1                                     ]                                     =                                     a[                                     abs                                     (a[i])                                     -                                     1                                     ]                                     *                                     (                                     -                                     1                                     )                       
                                                 i                                     =                                     i                                     +                                     1                       
                                   
                                                 return                                     sum                                     ;                       
                                   
                                   
                         # Driver code                       
                         a                                     =                                     [                                     5                                     ,                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     6                                     ,                                     7                                     ,                                     3                                     ,                                     6                                     ,                                     7                                     ]                       
                         n                                     =                                     len                                     (a)                       
                         print                                     (sumOfDistinct(a, n))                       
                                   
                         # This code is contributed by Nikita Tiwari.                       

C#

                         // C# program to find sum of distinct                       
                         // elements in sorted order                       
                         using                                     System;                       
           
                         class                                     GFG{                       
                                   
                                                 // Returns sum of distinct elements                       
                                                 // in arr[] assuming that elements                       
                                                 // in a[] are in range from 1 to n                       
                                                 static                                     int                                     sumOfDistinct(                                     int                                     []a,                                     int                                     n)                       
                                                 {                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                   
                                                 // If element appears first time                       
                                                 if                                     (a[Math.Abs(a[i]) - 1] >= 0) {                       
                                                 sum += Math.Abs(a[i]);                       
                                                 a[Math.Abs(a[i]) - 1] *= - 1;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     sum;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []a = {5, 1, 2, 4, 6, 7, 3, 6, 7};                       
                                                 int                                     n = a.Length;                       
                                                 Console.Write(sumOfDistinct(a, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal                       

PHP

                         <?php                       
                         // PHP program to find sum of                       
                         // distinct elements                       
           
                         // Returns sum of distinct                       
                         // elements in arr[] assuming                       
                         // that elements in a[] are                       
                         // in range from 1 to n.                       
                         function                                     sumOfDistinct(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                                 $sum                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                   
                                                 // If element appears first time                       
                                                 if                                     (                                     $a                                     [                                     abs                                     (                                     $a                                     [                                     $i                                     ]) - 1] >= 0)                       
                                                 {                       
                                                 $sum                                     +=                                     abs                                     (                                     $a                                     [                                     $i                                     ]);                       
                                                 $a                                     [                                     abs                                     (                                     $a                                     [                                     $i                                     ]) - 1] *= -1;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     $sum                                     ;                       
                         }                       
           
                                                 // Driver code                       
                                                 $a                                     =                                     array                                     (5, 1, 2, 4, 6, 7, 3, 6, 7);                       
                                                 $n                                     = sizeof(                                     $a                                     );                       
                                                 echo                                     sumOfDistinct(                                     $a                                     ,                                     $n                                     ) ;                       
           
                         // This code is contributed by nitin mittal                       
                         ?>                       

Javascript

                         <script>                       
                         // java script  program to find sum of                       
                         // distinct elements                       
           
                         // Returns sum of distinct                       
                         // elements in arr[] assuming                       
                         // that elements in a[] are                       
                         // in range from 1 to n.                       
                         function                                     sumOfDistinct(a, n)                       
                         {                       
                                                 let sum = 0;                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // If element appears first time                       
                                                 if                                     (a[Math.abs(a[i]) - 1] >= 0) {                       
                                                 sum += Math.abs(a[i]);                       
                                                 a[Math.abs(a[i]) - 1] *= -1;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     sum;                       
                         }                       
           
                                                 // Driver code                       
                                                 let a = [5, 1, 2, 4, 6, 7, 3, 6, 7];                       
                                                 let n = a.length;                       
                                                 document.write( sumOfDistinct(a, n));                       
           
                                   
                         //contributed by bobby                       
           
                         </script>                       

输出：

时间复杂度：O（n）辅助空间：O（1）本文由 埃克塔·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章