Знайдзіце суму масіваў, якія не паўтараюцца (розныя) элементы


Узровень складанасці Лёгка
Часта пытаюцца ў Кіслародны кашалёк
масіў гашыш хэшавання сартаванне

Пастаноўка праблемы

Улічваючы цэлалікавы масіў, A [] з паўтаральнымі элементамі, задача "Знайсці суму не паўтаральных элементаў (розных) элементаў у масіве" просіць знайсці суму ўсіх розных элементаў у масіве. Такім чынам, проста дадайце лічбы, якія не паўтараюцца ў масіве.

Прыклад

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.

код

Код C ++

#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

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. Такім чынам, складанасць часу O (N ^ 2).

Касмічная складанасць

Мы не займаем лішняга месца, таму касмічная складанасць O (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}

Табліца злева - наш уваходны масіў, а фіялетавы колер паказвае на бягучы індэкс.

Табліца справа - хэш-табліца

Знайдзіце суму масіваў, якія не паўтараюцца (розныя) элементы

Знайдзіце суму масіваў, якія не паўтараюцца (розныя) элементы

код

Код C ++

#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

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

Аналіз складанасці

Часовая складанасць

Мы паўтараем масіў толькі адзін раз, і складанасць часу функцыі ўстаўкі ў неўпарадкаваным наборы роўная O (1), таму агульная складанасць часу роўная O (N).

Касмічная складанасць

Мы ўзялі дадатковую хэш-табліцу, каб наша касмічная складанасць была O (N).