고유 한 요소가있는 부분 배열

난이도 중급
자주 묻는 질문 시스코 무료 타임즈 인터넷 조호 (Zoho)
배열 해시 해싱조회수 102

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

문제 정책

"고유 한 요소가있는 하위 배열"은 정수 요소의 배열이 제공됨을 나타냅니다. 문제 설명은 모든 요소가 서로 다른 연속 하위 배열 길이의 합을 구하도록 요청합니다.

arr[] = {3, 1, 2, 1}
4

설명 : 하위 배열은 ⇒ (3, 1, 2), (3, 1), (1, 2), (2,1), (3), (1), (2), (1)입니다.

모든 요소의 총 길이는 (3 + 2 + 2 + 2 + 1 + 1 + 1 + 1) = 10입니다.

고유 한 요소가있는 부분 배열

arr[] = {3, 5, 8, 9}
20

설명 : 하위 배열은 ⇒ (3), (5), (8), (9), (3, 5), (5, 8), (8, 9), (3, 5, 8), (5, 8, 9), (3, 5, 8, 9)

모든 요소의 총 길이는 (1 + 1 + 1 + 1 + 2 + 2 + 2 +3 +3 +4) = 10입니다.

고유 한 요소가있는 부분 배열을 찾는 알고리즘

1. Declare a map.
2. Set output and j to 0.
3. Traverse the array from i=0 to i<n(length of an array).
  1. While j is less than n and if a set doesn’t contain the value of arr[j].
    1. Insert all the values of arr [j].
  2. Update the output to output +=((j - i) * (j - i + 1))/2.
  3. Remove the arr[i] from Set.
4. Return output.

설명

우리는 정수 정렬. 우리의 임무는 모든 길이의 합을 찾는 것입니다. 하위 배열 연속적이고 고유 한 요소 만 있습니다. 우리는 세트. 세트는 세트에서 복사되거나 공통 요소를 제거하는 기능을 제공합니다. j를 0으로 설정하고 출력을 0으로 설정합니다.

어레이를 탐색하여 시작하고 while 루프. j의 값을 0으로 설정하고 내부 while 루프 j를 증가시키면서 루프를 횡단합니다. 여기에 몇 가지 조건을 설정합니다. j는 n보다 작습니다. 즉, 배열의 길이와 Set에 arr [j] 값이 포함되어있는 경우에도 마찬가지입니다. 예를 들어 보겠습니다.

도착 [] = {3, 1, 2, 1}

우리는 한 번에 각 요소를 선택하는 배열을 순회 할 것입니다. 처음에 3을 선택한다고 가정합니다. arr [j]에서 아이디어는이 3이 시작되는 동안 외부 루프를 일정하게 유지하는 것입니다. while 루프, j는 0으로 초기화되고 set는 처음으로 3을 포함하지 않으므로 a while 루프 arr [j]는 3을 의미하고 j ++를 증가 시키면 다음 요소를 1로 선택합니다. 세트 포함하지 않으므로 세트에 삽입되고 2가되고 1이되지만 이번에는 1이 이미 루프에 있으므로 while 루프.

이제 루프에서 나올 때 j의 값을 증가 시켰으므로 이에 따라 출력을 업데이트 할 것입니다. 그리고 추가 순회를 위해 배열의 요소를 제거해야합니다. 그래야 하위 배열에서 개별 요소의 합의 가능한 길이를 알 수 있습니다. 마지막으로 해당 출력을 반환합니다.

암호

고유 한 요소가있는 하위 배열을 찾는 C ++

#include<iostream>
#include<unordered_set>

using namespace std;

int getLength(int arr[], int n)
{
    unordered_set<int> SET;

    int j = 0, output = 0;
    for (int i=0; i<n; i++)
    {
        while (j < n && SET.find(arr[j]) == SET.end())
        {
            SET.insert(arr[j]);
            j++;
        }
        output += ((j - i) * (j - i + 1))/2;
        SET.erase(arr[i]);
    }
    return output;
}
int main()
{
    int arr[] = {3, 1, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getLength(arr, n);
    return 0;
}
13

고유 한 요소가있는 하위 배열을 찾는 Java 코드

import java.util.Set;
import java.util.HashSet;

class LengthOfDistinctElements
{
    public static int getLength(int[] arr, int n)
    {
        Set<Integer> SET = new HashSet<>();
        int j = 0, output = 0;
        for (int i = 0; i < n; i++)
        {
            while (j < n && !SET.contains(arr[j]))
            {
                SET.add(arr[j]);
                j++;
            }
            output += ((j - i) * (j - i + 1)) / 2;
            SET.remove(arr[i]);
        }
        return output;
    }
    public static void main(String[] args)
    {
        int[] arr = { 3, 1, 2,1  };
        int n = arr.length;
        System.out.println(getLength(arr, n));
    }
}
13

복잡성 분석

시간 복잡성

우리는 배열을 순회하고 있으며 HashSet을 사용하면 O (1)에서 삽입 및 기타 작업을 수행 할 수 있습니다. 따라서 우리는 의 위에) 시간 복잡성 "엔" 배열의 요소 수입니다.

공간 복잡성

N 개의 요소 만 저장했기 때문에 선형 공간 복잡성을 달성했습니다. 의 위에) 어디에 "엔" 배열의 요소 수입니다.

균열 시스템 설계 인터뷰
Translate »