配列内の非反復要素(個別)要素の合計を検索します


難易度 簡単に
よく聞かれる 酸素ウォレット
配列 ハッシュ ハッシング 並べ替え(ソート)

問題文

整数配列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のXNUMXつのネストされたループがあります。 したがって、時間計算量は 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

複雑さの分析

時間の複雑さ

配列を1回だけ反復し、順序付けされていないセットの挿入関数の時間計算量はO(XNUMX)であるため、合計時間計算量は次のようになります。 オン)。

スペースの複雑さ

スペースの複雑さが オン)。