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

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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

반복되는 요소가있는 정수 배열 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 »