배열에서 반복되지 않는 요소 (고유 한) 요소의 합계 찾기

난이도 쉽게
자주 묻는 질문 Oxigen 지갑
배열 해시 해싱 정렬조회수 45

문제 정책

반복되는 요소가있는 정수 배열 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)이므로 총 시간 복잡도는 의 위에).

공간 복잡성

추가 해시 테이블을 가져 왔으므로 공간 복잡성은 의 위에).

 

Translate »