세 번째 최대 수 Leetcode 솔루션


난이도 쉽게
자주 묻는 질문 아마존 페이스북 서비스 구글
배열

제목에서 알 수 있듯이 목표는 주어진 값에서 세 번째 최대 정수를 찾는 것입니다. 정렬 정수 우리는 뚜렷한 배열의 세 번째 최대 정수입니다. 고유 한 세 번째 최대 정수가없는 경우 배열의 최대 정수를 반환합니다.

Array = {1 , 3 , 2 , -2 , -4 , -9}
1

설명

첫 번째 최대 값은 3, 두 번째 최대 값은 2, 세 번째 최대 값은 1입니다. 따라서 1을 인쇄합니다.

Array = {1 , 1 , 3}
3

설명

첫 번째 최대 값은 3이고 두 번째 최대 값은 1이지만 아니 세 번째 최대 값은 여기서 1을 두 번째 최대 값으로 간주하기 때문입니다.

접근 (정렬)

전체 배열을 정렬하고 세 번째 구별 그것에서 시작하는 정수 뒤로. 배열에 중복 항목이있을 수 있으므로 단순히 Array [N – 3]을 반환 할 수 없습니다. 우리가 찾지 못하면 3 배열에있는 고유 한 정수의 경우 최대 요소 인 마지막 요소를 반환합니다. 더 나은 이해를 위해 주어진 알고리즘을 따르십시오.

세 번째 최대 수 Leetcode 솔루션

암호알고리즘

  1. 함수 만들기 thirdMax () 필요한 정수 반환
  2. thirdMax () 주어진 배열에서 세 번째 고유 한 최대 정수를 반환합니다. a
  3. 배열 정렬
  4. 변수 초기화, idx 배열의 마지막 인덱스를 저장하고 distinctCount 뒤에서 구별되는 요소를 세다
  5. 동안 idx> = 0:
    • 증가 distinctCount
    • 초기화 a [idx]와 같은 값을 갖는 인덱스를 반복합니다.
    • 이전 요소는 idx a [idx]와 같은 값을 가지며 나는> = 0:
      • 감소 i
    • If i == -1, 전체 배열을 순회했음을 의미합니다.
      • 배열에 1 개의 별개의 요소가 없었기 때문에 a [n – 3], 최대 요소를 반환합니다.
    • 양수인 idx = 나 다음 최대 정수 세트로 이동
    • If distinctCount 2와 같고
      • 현재 요소 (a [idx])보다 2 개의 더 큰 요소를 확인했음을 의미합니다.
      • 현재 요소, a [idx] 반환
  6.  함수 구문을 위해 -1을 반환합니다.
  7. 결과 인쇄

세 번째 최대 Leetcode 솔루션 구현

C ++ 프로그램

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

int thirdMax(vector <int> &a)
{
    int n = a.size();
    sort(a.begin() , a.end());

    int idx = n - 1 , i , distinctCount = 0;

    while(idx >= 0)
    {
        distinctCount++;
        i = idx - 1;
        //to check all the values with same value as a[idx]
        while(i >= 0 && a[i] == a[idx])
            i--;

        //no third distinct element
        if(i == -1)
            return a[n - 1];
        idx = i;

        //found 2 bigger elements before?
        if(distinctCount == 2)
            return a[idx];
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 2 , -2 , -4 , -9};
    cout << thirdMax(a) << '\n';
}

자바 프로그램

import java.util.Arrays;

class third_max
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 2 , -2 , -4 , -9};
        System.out.println(thirdMax(a));
    }

    static int thirdMax(int[] a)
    {
        int n = a.length;
        Arrays.sort(a);

        int idx = n - 1 , i , distinctCount = 0;

        while(idx >= 0)
        {
            distinctCount++;
            i = idx - 1;
            //to check all the values with same value as a[idx]
            while(i >= 0 && a[i] == a[idx])
                i--;

            //no third distinct element
            if(i == -1)
                return a[n - 1];
            idx = i;

            //found 2 bigger elements before?
            if(distinctCount == 2)
                return a[idx];
        }
        return -1;
    }
}
1

세 번째 최대 수 Leetcode 솔루션의 복잡성 분석

시간 복잡성

O (NlogN), N = 전체 배열을 정렬 할 때 배열의 크기입니다.

공간 복잡성

O (1) 일정한 메모리 공간 만 사용하기 때문입니다.

접근 (최적)

여기서 최적의 접근 방식은 배열에 첫 번째, 두 번째 및 세 번째 최대 정수를 저장할 세 개의 값만 유지하는 것입니다. 그러나 항상 고유 한 요소를 최대 값으로 간주해야하는 몇 가지 기본 사례가 있습니다. 이 목적을 위해, 세트 중복 요소를 항상 제거 할 수 있도록 사용할 수 있습니다. 배열을 반복하고 크기를 유지할 수 있습니다. 세트 매 반복 후 3으로. 삽입 후 3 개 이상의 요소가 포함 된 경우 가장 적은 요소를 팝업하여 XNUMX 개를 포함합니다. 뚜렷한 가장 큰 결국 요소. 크기가 결국 3보다 작 으면 최대 값을 반환합니다.

암호알고리즘

  1. 다시 같은 기능을 사용합니다. thirdMax () 우리 문제를 해결하기 위해
  2. 최대 정수를 저장하도록 집합을 초기화합니다.
  3. 매회마다 요소 배열에서 :
    • 세트에 추가
    • 세트의 크기가 3을 초과하는 경우
      • 세트에서 가장 적은 요소 지우기 / 제거
  4. 세트의 크기가 3과 같으면
    • 그것에서 최소 요소를 반환
  5. 다른
    • 그것의 최대 요소를 반환
  6. 결과 인쇄

세 번째 최대 Leetcode 솔루션 구현

C ++ 프로그램

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

int thirdMax(vector <int> &a)
{
    set <int> maxElements;
    for(int &element : a)
    {
        maxElements.insert(element);
        if(maxElements.size() > 3)
            maxElements.erase(*maxElements.begin());
    }
    if(maxElements.size() == 3)
        return *maxElements.begin();

    return *prev(maxElements.end());
}

int main()
{
    vector <int> a = {1 , 3 , 2 , -2 , -4 , -9};
    cout << thirdMax(a) << '\n';
}

자바 프로그램

import java.util.*;

class third_max
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 2 , -2 , -4 , -9};
        System.out.println(thirdMax(a));
    }

    static int thirdMax(int[] a)
    {
        Set <Integer> maxElements = new HashSet <>();
        for(int element : a)
        {
            maxElements.add(element);
            if(maxElements.size() > 3)
                maxElements.remove(Collections.min(maxElements));
        }

        if(maxElements.size() == 3)
            return Collections.min(maxElements);
        return Collections.max(maxElements);
    }
}
1

세 번째 최대 수 Leetcode 솔루션의 복잡성 분석

시간 복잡성

의 위에) 단일 패스로 배열을 반복합니다. 세트에서 요소의 삭제 및 삽입은 매 반복 후 최대 3 개의 요소를 유지하므로 일정한 시간이 걸립니다. 여기, N = 배열의 크기.

공간 복잡성

O (1) 일정한 메모리 공간 만 사용하기 때문입니다.