በአንድ ድርድር ውስጥ የማይደጋገሙ አካላት (የተለዩ) አካላት ድምር ይፈልጉ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ ኦክሲጀን የኪስ ቦርሳ
ሰልፍ ሃሽ ሃምሽንግ መደርደር

የችግሩ መግለጫ

ኢንቲጀር ድርድር ፣ ሀ [] ከተደጋገሙ አካላት ጋር “የማይደገሙ አባላትን ድምር (ልዩ) ንጥረ ነገሮችን በአንድ ድርድር ውስጥ ያግኙ”) ችግሩ በምድቡ ውስጥ ያሉትን ሁሉንም የተለዩ አካላት ድምር እንዲያገኝ ይጠይቃል። ስለዚህ ፣ በድርድሩ ውስጥ የማይደገሙ ቁጥሮችን በቀላሉ ያክሉ።

ለምሳሌ

A[]={1, 4, 2, 1, 5, 2, 3, 2}
11

ማብራሪያ-የማይደጋገሙ አካላት -4 ፣ 5 ፣ 3. ስለዚህ የእነሱ ድምር = 4 + 5 + 3 = 11 ነው ፡፡

የጭካኔ ኃይል

በአንድ ድርድር ውስጥ የማይደጋገሙ አካላት (የተለዩ) አካላት ድምር ለማግኘት ዋና ሀሳብ

ለእያንዳንዱ ንጥረ ነገር ፣ እሴቱ ተመሳሳይ የሆነ ወይም የሌለበት ሌላ አካል ካለ ያረጋግጡ እና አሁን ካለው ጠቋሚ ያነሰ ጠቋሚ ያለው። እንደዚህ አይነት አካል ከሌለ የአሁኑን ንጥረ ነገር ወደ መልሱ ያክሉ አለበለዚያ ይዝለሉት።

አልጎሪዝም

1. Run a loop for I in range 0 to n-1 
    1. Run a loop for j in range 0 to i 
        1. If j==i, add A[i]. 
        2. If A[i] is equal to A[j], break out from this loop. 
    2. Return.

ኮድ

ሲ ++ ኮድ

#include <bits/stdc++.h>
using namespace std;
void sumOfDistinctElements(vector<int> A)
{
    int n = A.size();
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == i)
            {
                sum += A[i];
            }
            if (A[i] == A[j])
            {
                break;
            }
        }
    }
    cout << "Sum of distinct Elements in the array is: " << sum << endl;
    return;
}
int main()
{
    vector<int> A = {1, 4, 2, 1, 5, 2, 3, 2};
    sumOfDistinctElements(A);
    return 0;
}
Sum of distinct Elements in the array is: 15

የጃቫ ኮድ

public class Main
{   
    static void sumOfDistinctElements(int A[])
    {
        int n = A.length;
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (j == i)
                {
                    sum += A[i];
                }
                if (A[i] == A[j])
                {
                    break;
                }
            }
        }
        System.out.println("Sum of distinct Elements in the array is: " + sum);
        return;
    }
  public static void main(String[] args) {
    int A[] = {1, 4, 2, 1, 5, 2, 3, 2};
        sumOfDistinctElements(A);
  }
}
Sum of distinct Elements in the array is: 15

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

እያንዳንዳቸው መጠናቸው n ሁለት የተጠረዙ ቀለበቶች አሉን ፡፡ ስለዚህ የጊዜ ውስብስብነቱ ነው ኦ (N ^ 2)

የቦታ ውስብስብነት

ምንም ተጨማሪ ቦታ አንወስድም ስለዚህ የቦታ ውስብስብነት ነው ኦ (1).

የተመቻቸ አቀራረብ

በአንድ ድርድር ውስጥ የማይደጋገሙ አካላት (የተለዩ) አካላት ድምር ለማግኘት ዋና ሀሳብ

ቀደም ሲል ያተምናቸውን ንጥረ ነገሮች የሚያከማች የሃሽ ሰንጠረዥን እንጠብቃለን ፡፡ ስለዚህ እኛ ድርድርን እናካሂዳለን ፣ በሐሽ ሰንጠረዥ ውስጥ የማይገኝ በድርድሩ ውስጥ አንድ ንጥረ ነገር ካገኘን ያንን ንጥረ ነገር በመልሱ ላይ እንጨምረዋለን እና በሃሽ ሰንጠረዥ ውስጥ እንጨምረዋለን ፣ ካልሆነ ያንን ንጥረ ነገር እናልፈዋለን

አልጎሪዝም

1. Declare a hash table.
2. Run a loop for I in range 0 to n-1:
    1. If A[i] is not present in the hash table, then add it and insert it in the hash table.
    2. If A[i] is not present in the hash table then skip it.
3. Return.

ለምሳሌ

እንበል

A[]={3, 3, 1, 2 ,1}

በግራ በኩል ያለው ሰንጠረዥ የእኛን የግብዓት ድርድር እና ሐምራዊ ቀለም ነጥቦችን ወደ የአሁኑ ማውጫ ነው ፡፡

በቀኝ በኩል ያለው ሰንጠረዥ እ.ኤ.አ. ሃሽ ሠንጠረዥ

በአንድ ድርድር ውስጥ የማይደጋገሙ አካላት (የተለዩ) አካላት ድምር ይፈልጉ

በአንድ ድርድር ውስጥ የማይደጋገሙ አካላት (የተለዩ) አካላት ድምር ይፈልጉ

ኮድ

ሲ ++ ኮድ

#include <bits/stdc++.h>
using namespace std;
void sumOfDistinctElements(vector<int> A)
{
    int n = A.size();
    int sum = 0;
    unordered_set<int> hash_table;
    for (int i = 0; i < n; i++)
    {
        if (hash_table.count(A[i]) == 0) //hash_table.count(x) returns 1 if x is present in the hash_table otherwise returns 0
        {
            hash_table.insert(A[i]);
            sum += A[i];
        }
    }
    cout << "Sum of distinct Elements in the array is: " << sum << endl;
    return;
}
int main()
{
    vector<int> A = {1, 4, 2, 1, 5, 2, 3, 2};
    sumOfDistinctElements(A);
    return 0;
}
Sum of distinct Elements in the array is: 15

የጃቫ ኮድ

import java.util.*;
public class Main
{   
    static void sumOfDistinctElements(int A[])
    {
        int n = A.length;
        int sum = 0;
        HashSet<Integer> hash_table = new HashSet<Integer>(); 
        for (int i = 0; i < n; i++) 
        { 
            if (!hash_table.contains(A[i])) 
            { 
                sum += A[i]; 
                hash_table.add(A[i]); 
            } 
        } 
        System.out.println("Sum of distinct Elements in the array is: " + sum);
        return;
    }
  public static void main(String[] args) {
    int A[] = {1, 4, 2, 1, 5, 2, 3, 2};
        sumOfDistinctElements(A);
  }
}
Sum of distinct Elements in the array is: 15

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ድርድርን አንድ ጊዜ ብቻ እናስተላልፋለን እና ባልተስተካከለ ስብስብ ውስጥ የማስገቢያ ተግባር ውስብስብነት (1) ነው ፣ ስለሆነም አጠቃላይ የጊዜ ውስብስብነት ኦ (ኤን)

የቦታ ውስብስብነት

ተጨማሪ የሃሽ ጠረጴዛ ወስደናል ስለዚህ የእኛ የቦታ ውስብስብነት ነው ኦ (ኤን)