배열에서 인접한 고유 요소

난이도 쉽게
자주 묻는 질문 Coursera 드 쇼 인상 IBM 쿨리 자 나가로 운영 오요 룸 조호 (Zoho)
배열조회수 76

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

문제 정책

우리가 정수 정렬. "배열에서 인접 요소 구분"문제는 가능한 경우 배열에서 두 개의 인접 또는 인접 요소를 교체하여 모든 인접 숫자가 구별되는 배열을 얻을 수 있는지 여부를 확인하고 "YES ”그렇지 않으면“NO”를 인쇄합니다.

arr[] = { 3,5,5,3,5}
YES

이 예에서 우리는 arr [2]와 arr [3]을 각각 5와 2로 바꿔서 서로 다른 인접 숫자의 배열을 얻을 수 있습니다.

배열에서 인접한 고유 요소

arr[] = {3 , 5,  3, 3 }
NO

설명

값을 바꾼 후에도 원하는 배열을 얻을 수 없습니다.

배열의 고유 인접 요소에 대한 알고리즘

1. Declare a map.
2. Count and store the frequencies of each element of the array.
3. Set maxFreq to 0.
4. Get the maximum frequency of a number from the map.
5. Check if maxFreq is greater than the half-length of the array, means maxFreq >(n+1) / 2.
    1. If true, then print NO.
    2. Else print YES.

설명

정수 배열이 주어집니다. 우리는 별개의 인접 요소가 가능한 배열을 얻는 지 확인하라는 요청을 받았습니다. 이는 그러한 배열이 가능하지 않으면 NO를 인쇄하고 그렇지 않으면 YES를 인쇄한다는 것을 의미합니다. 이제 원하는 배열을 얻기 위해 얼마나 많은 숫자를 교체해야하는지 확인해야합니다. 각 요소의 발생을 확인하고 최대 발생이 배열 길이의 절반보다 크지 않아야합니다. 배열의 길이가 5로 주어질 경우 요소가 배열에서 3 번 발생하는 경우. 그런 다음 첫 번째, 세 번째 및 다섯 번째 위치에서 어레이를 재 배열 할 수 있습니다. 따라서 배열에서 서로 다른 인접 요소를 얻을 수 있습니다.

우리가 할 것은 지도. 그런 다음 배열을 탐색하고 각 요소의 빈도를 계산합니다. 지도에 각 요소의 모든 주파수를 동시에 저장합니다. 5 개의 숫자로 구성된 배열이 있다고 가정합니다. 그중 0 개는 배열에서 두 번 발생하고 다른 숫자는 한 번 발생했습니다. 그래서 우리는 배열의 각 요소의 주파수를 저장할 것입니다. 요소의 모든 주파수를 저장 한 후. maxFreq 변수를 XNUMX으로 설정합니다. 여기에 최대 주파수를 찾은 후 요소의 최대 주파수 수를 저장합니다.

이를 위해지도를 순회하고 이전에 저장된 빈도보다 더 큰 빈도가 있는지 각 요소를 확인합니다. 이를 통해 최대 수를 주파수로 사용하고 해당 주파수가 어레이 길이의 절반보다 큰지 확인합니다. true이면 NO를 인쇄하고 그렇지 않으면 YES를 인쇄하십시오.

암호

배열 문제의 고유 인접 요소에 대한 C ++ 코드

#include<bits/stdc++.h>
using namespace std;
void areDistinctAdjacent(int a[], int n)
{
    unordered_map<int, int> MAP;
    for (int i = 0; i < n; ++i)
        MAP[a[i]]++;
    int maxFreq = 0;
    for (int i = 0; i < n; ++i)
        if (maxFreq < MAP[a[i]])
            maxFreq = MAP[a[i]];
    if (maxFreq > (n + 1) / 2)
        cout << "NO";
    else
        cout << "YES";
}
int main()
{
    int arr[] = { 3,5,5,3,5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    areDistinctAdjacent(arr, n);
    return 0;
}

 

YES

배열 문제의 고유 인접 요소에 대한 Java 코드

import java.util.HashMap;
import java.util.Map;

class adjacentDistinctElement
{
    static void areDistinctAdjacent(int a[], int n)
    {
        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();

        for (int i = 0; i < n; ++i)
        {
            if(MAP.containsKey(a[i]))
            {
                int x = MAP.get(a[i]) + 1;
                MAP.put(a[i],x);
            }
            else
            {
                MAP.put(a[i],1);
            }

        }
        int maxFreq = 0;

        for (int i = 0; i < n; ++i)
            if (maxFreq < MAP.get(a[i]))
                maxFreq = MAP.get(a[i]);

        if (maxFreq > (n + 1) / 2)
        {
            System.out.println("NO");
        }
        else
        {
            System.out.println("YES");
        }
    }
    public static void main (String[] args)
    {
        int arr[] = { 3,5,5,3,5 };
        int n = arr.length;
        areDistinctAdjacent(arr, n);
    }
}

YES

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. Hashmap을 사용했기 때문에 선형 시간 복잡성을 달성 할 수 있습니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 해시 맵을 사용했기 때문에 요소의 빈도를 저장했습니다. 최악의 경우에는 모두 다른 요소가있을 수 있습니다. 그러면 N 개의 키-값 쌍이 생깁니다. 그래서 우리는 O (N) 공간 복잡성을 가지고 있습니다.

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