Bir sıra içində təkrarlanmayan elementlərin (fərqli) elementlərin cəmini tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Oxigen cüzdanı
Geyim Sükut Hashing çeşidləyiciBaxılıb 45

Problem bəyanat

Təkrarlanan elementləri olan A [] tam ədədi verildiyi halda, “Bir sıra içərisində təkrarlanmayan elementlərin (fərqli) elementlərin cəmini tap” problemi, massivdəki bütün fərqli elementlərin cəmini tapmağı xahiş edir. Beləliklə, sadəcə serialda təkrarlanmayan nömrələri əlavə edin.

misal

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

İzahat: Təkrarlanmayan elementlər bunlardır: 4, 5, 3. Beləliklə onların cəmi = 4 + 5 + 3 = 11.

Gücün tətbiqi

Bir sıra içərisində təkrarlanmayan elementlərin (fərqli) elementlərin cəmini tapmaq üçün əsas fikir

Hər element üçün, dəyəri eyni olan və indiki indeksdən kiçik bir indeksə sahib olan başqa bir elementin olub olmadığını yoxlayın. Belə bir element yoxdursa, cari elementi cavaba əlavə edin, əks halda onu atlayın.

Alqoritm

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.

Kodu

C ++ kodu

#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

Java kodu

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

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

Hər birinin ölçüsü n olan iki iç içə döngəmiz var. Yəni zamanın mürəkkəbliyi O (N ^ 2).

Kosmik mürəkkəblik

Əlavə yer almırıq, ona görə də yerin mürəkkəbliyi O (1).

Optimallaşdırılmış yanaşma

Bir sıra içərisində təkrarlanmayan elementlərin (fərqli) elementlərin cəmini tapmaq üçün əsas fikir

Artıq yazdırdığımız elementləri saxlayacaq bir hash masası saxlayacağıq. Beləliklə, massivi təkrarlayacağıq, əgər massivdə hash cədvəlində olmayan bir element tapmışıqsa, o elementi cavaba əlavə edib hash cədvəlinə daxil edəcəyik, əks halda həmin elementi atlayacağıq.

Alqoritm

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.

misal

Deyək

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

Sol tərəfdəki cədvəl giriş dizimizdir və cari indeksə bənövşəyi rəng nöqtələridir.

Sağdakı cədvəl hash masa

Bir sıra içində təkrarlanmayan elementlərin (fərqli) elementlərin cəmini tapınPin

Bir sıra içində təkrarlanmayan elementlərin (fərqli) elementlərin cəmini tapınPin

Kodu

C ++ kodu

#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

Java kodu

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

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

Massivi yalnız bir dəfə təkrarlayırıq və nizamsız çoxluqda insert funksiyasının zaman mürəkkəbliyi O (1) olduğu üçün ümumi zaman mürəkkəbliyi O (N).

Kosmik mürəkkəblik

Məkan mürəkkəbliyimiz olduğu üçün əlavə bir hash masası götürdük O (N).

 

Translate »