대다수 요소 II Leetcode 솔루션-TutorialCup

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

이 문제에서 우리는 정렬 정수 목표는 이상 발생하는 모든 요소를 찾는 것입니다. ⌊N / 3⌋ N = 배열의 크기이고 ⌊ ⌋는 플로어 연산자 인 배열의 시간입니다. 이러한 요소의 배열을 반환해야합니다.

요소 범위 : -10 ^ 9 에 10 ^ 9

차례

예

Array = {1 , 2 , 3 , 3 , 2}

2 3

설명: ⌊N / 3⌋ = ⌊5 / 3⌋ = 1. 이제 정수 2와 3은 주파수가 2와 같고 1이 더 큽니다. 그래서 우리는 그것들을 인쇄합니다.

Array = {1 , 2 , 3 , 4}

No majority elements

설명 : 이 경우 주파수가 1보다 큰 요소를 찾지 못했습니다. 따라서 "과반수 요소 없음"을 인쇄합니다.

접근 (저장 주파수)

제목에서 알 수 있듯이 해시 테이블을 사용하여 배열에있는 모든 요소의 빈도를 저장 한 다음 빈도가 다음보다 큰 요소를 확인할 수 있습니다. ⌊N / 3⌋. 이런 식으로 조건을 충족하는 모든 요소를 찾을 수 있습니다.

암호알고리즘

HashMap 초기화주파수 배열과 목록 / 벡터에있는 요소의 빈도를 저장합니다. 결과 대부분의 요소를 저장하기 위해
모든 요소에 대해 i 배열에서 :
- 빈도 증가 : frequency [i] ++ (또는 아직없는 경우 1로 설정)
매회마다 키 해시 맵에서 :
1. If 주파수 [키] > N / 3
  1. 그것을 추가하십시오 결과
목록 반환 결과

Majority Element II Leetcode 솔루션 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

vector<int> majorityElement(vector<int>& a)
{
    int N = a.size();
    vector <int> result;
    unordered_map <int , int> frequency;
    for(int &x : a)
        frequency[x]++;
    for(auto &x : frequency)
        if(x.second > N / 3)
            result.emplace_back(x.first);
    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 3 , 3 , 2};
    vector <int> result = majorityElement(a);
    if(result.empty())
        cout << "No majority elements\n";
    else
        for(int &x : result)
            cout << x << " ";
    return 0;
}

자바 프로그램

import java.util.*;

class majority_element_ii
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 3 , 3 , 2};
        List <Integer> result = majorityElement(a);
        if(result.size() == 0)
            System.out.println("No majority elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> majorityElement(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashMap <Integer , Integer> frequency = new HashMap <>();

        for(int i = 0 ; i < a.length ; i++)
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);

        for(Map.Entry i : frequency.entrySet())
        {
            Integer value = (int)i.getValue() , key = (int)i.getKey();
            if((int)value > ((a.length) / 3))
                result.add(key);
        }
        return result;
    }
}

2 3

다수 요소 II Leetcode 솔루션의 복잡성 분석

시간 복잡성

의 위에) 주파수를 업데이트하기 위해 전체 배열을 한 번 탐색합니다. N = 배열의 크기.

공간 복잡성

의 위에) 해시 테이블을 사용하여 주파수를 저장합니다.

접근하다(Boyer-Moore 투표 알고리즘)

여기서 가장 먼저 주목해야 할 점은 다음보다 큰 주파수를 가진 최대 2 개의 요소가 배열의 ⌊N / 3⌋. 따라서이 문제는 다수 요소 있는 문제 2 이번에는 대부분의 요소.

Boyer-Moore의 투표 알고리즘을 사용하여 이미 다수 요소 문제를 해결했습니다. 단일 다수 요소의 경우 현재 요소가 후보인지 여부를 비교하여 알고리즘을 사용할 수 있습니다. 그러나이 경우 두 개의 잠재적 인 다수 요소를 보유하고 카운터를 병렬로 업데이트해야합니다. 이 직감의 도움으로 다음과 같이 조건을 설정할 수 있습니다.

배열의 요소 범위 밖에있는 임의의 두 후보를 설정합니다.
요소가 후보 중 하나와 같으면 카운터를 증가시킵니다.
한 후보의 카운터가 다음과 같으면 0 언제든지 현재 요소를 후보로 설정합니다. if 이 현재 요소는 다른 후보가 아닙니다.
현재 요소가 두 후보 중 하나와 같지 않으면 두 후보의 카운터를 줄입니다.

이러한 방식으로 첫 번째 후보가 다른 후보에 영향을주지 않고 배열에서 두 개의 다른 후보를 병렬로 계속 유지합니다. 그러나 이것은 우리가 끝낸 후보가 진정한 다수 요소가 아닐 수도 있습니다 ({1, 1, 2, 2, 3, 3}가 그러한 예입니다). 따라서 두 번째 패스를 실행하여 최종 후보의 빈도를 계산해야합니다. 이를 기반으로 다수 요소의 벡터를 반환 할 수 있습니다.