대다수 요소 II Leetcode 솔루션

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

이 문제에서 우리는 정렬 정수 목표는 이상 발생하는 모든 요소를 ​​찾는 것입니다. ⌊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