대다수 요소 II Leetcode 솔루션

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 Facebook 구글 Microsoft Zenefits
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 80

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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⌋. 이런 식으로 조건을 충족하는 모든 요소를 ​​찾을 수 있습니다.

암호알고리즘

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

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}가 그러한 예입니다). 따라서 두 번째 패스를 실행하여 최종 후보의 빈도를 계산해야합니다. 이를 기반으로 다수 요소의 벡터를 반환 할 수 있습니다.

암호알고리즘

  1. 초기화 캔디원Candtwo 두 후보와 그 주파수를 저장하기 위해 씨엔티원씨엔투 as 0.
  2. 모든 요소에 대해 배열에서 :
    • If candOne == i :
      • 씨엔티원++
    • 그렇지 않으면 캔드투 == i
      • 씨엔투++
    • 그렇지 않으면 cn하나 == 0
      • 양수인 i as 캔디원: candOne = 나
      • 개수를 1로 설정합니다. cntOne = 1
    • 그렇지 않으면 cnttwo == 0
      • candTwo = 나
      • cnt1 = XNUMX
    • 두 후보의 수를 줄입니다.
      • 씨엔티원–
      • 씨엔투-
  3. 두 번째 패스에 대해 카운트를 다시 XNUMX으로 설정합니다. cntOne = 0cnt0 = XNUMX
  4. 배열의 모든 요소에 대해 :
    • candOne과 같은 경우 :
      • cntOne ++
    • 그렇지 않으면 candTwo와 같은 경우 :
      • cntTwo ++
  5. 목록 / 벡터 초기화 결과 대부분의 요소 저장
  6. cntOne> N / 3 인 경우
    • 푸시 캔디원결과
  7. cntTwo> N / 3 인 경우
    • 푸시 캔드투결과
  8. 결과 인쇄

그림 :

대다수 요소 II Leetcode 솔루션

Majority Element II Leetcode 솔루션 구현

C ++ 프로그램

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

vector <int> majorityElement(vector <int> &a)
{
    vector <int> result;
    int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
    for(int &i : a)
    {
        if(candOne == i)
            cntOne++;
        else if(candTwo == i)
            cntTwo++;
        else if(cntOne == 0)
        {
            candOne = i;
            cntOne++;
        }
        else if(cntTwo == 0)
        {
            candTwo = i;
            cntTwo++;
        }
        else
        {
            cntOne--;
            cntTwo--;
        }
    }

    cntOne = 0;
    cntTwo = 0;
    for(int &i : a)
    {
        if(i == candOne)
            cntOne++;
        if(i == candTwo)
            cntTwo++;
    }

    if(cntOne > ((int)a.size()) / 3)
        result.push_back(candOne);
    if(cntTwo > ((int)a.size()) / 3)
        result.push_back(candTwo);

    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<>();

        int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
        for(int i : a)
        {
            if(candOne == i)
                cntOne++;
            else if(candTwo == i)
                cntTwo++;
            else if(cntOne == 0)
            {
                candOne = i;
                cntOne++;
            }
            else if(cntTwo == 0)
            {
                candTwo = i;
                cntTwo++;
            }
            else
            {
                cntOne--;
                cntTwo--;
            }
        }

        cntOne = 0;
        cntTwo = 0;
        for(int i : a)
        {
            if(i == candOne)
                cntOne++;
            if(i == candTwo)
                cntTwo++;
        }

        if(cntOne > (a.length) / 3)
            result.add(candOne);
        if(cntTwo > (a.length) / 3)
            result.add(candTwo);

        return result;
    }
}
3 2

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

시간 복잡성

의 위에) 입력에 관계없이 배열의 두 패스를 실행합니다. N = 배열의 크기.

공간 복잡성

O (1) 우리가 일정한 기억 공간으로.

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