جمع عناصر تکرار نشدنی (مجزا) را در یک آرایه پیدا کنید


سطح دشواری ساده
اغلب در Oxigen Wallet
صف مخلوط هشی کردن مرتب سازی

بیان مسأله

با توجه به یک آرایه صحیح ، 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

کد جاوا

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

کد جاوا

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) است ، بنابراین پیچیدگی زمان کل بر).

پیچیدگی فضا

ما یک جدول هش اضافی گرفتیم ، بنابراین پیچیدگی فضای ما بسیار زیاد است بر).