배열 Leetcode 솔루션에서 두 요소의 최대 곱

"배열에있는 두 요소의 최대 곱"문제에서 우리의 목표는 두 개의 인덱스를 찾는 것입니다. i 및 j 주어진 정수 배열에서 a, 제품 (a [i] – 1) * (a [j] – 1)이 최대가됩니다. 배열에는 2 개 이상의 요소가 있으며 모든 요소는 양수입니다. 필요한 제품이 정수 범위에 맞는 문제입니다. 최적을 위해 (a [i] – 1) * (a [j] – 1)의 값을 인쇄해야합니다. i & j.

예

a = {1 , 4 , 5 , 3 , 6 , 4}

2

설명

분명히 6과 5가 가장 크고 두 번째로 큰 숫자입니다. 따라서 product = (a [i] – 1) * (a [j] – 1) = 20입니다.

접근 (정렬)

제품 : (a [i] – 1) * (a [j] – 1) a [i]와 a [j]가 배열에서 가장 큰 두 요소 일 때 최대 값이됩니다. 가장 큰 두 요소를 포함하는 두 개의 인덱스 i와 j를 찾는 대신 종류 전에, 정렬 오름차순으로. 이렇게하면 가장 큰 두 요소가 끝에 있습니다. 따라서 제품 (a [n – 1] – 1) * (a [n – 2] – 1) 필요한 결과가 될 것입니다.

암호알고리즘

1. 배열 정렬
2. 결과 인쇄 : (a [n – 1] – 1) * (a [n – 2] – 1)

배열에서 두 요소의 최대 곱을 찾기위한 알고리즘 구현

C ++ 프로그램

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

int maxProduct(vector <int> &a)
{
    int n = a.size();
    sort(a.begin() , a.end());
    return ((a[n - 1] - 1) * (a[n - 2] - 1));
}


int main()
{
    vector <int> a = {1 , 4 , 5 , 3 , 6 , 4};
    cout << maxProduct(a) << '\n';
}

자바 프로그램

import java.util.Arrays;

class maximum_product
{
    public static void main(String args[])
    {
        int[] a = {1 , 4 , 5 , 3 , 6 , 4};
        System.out.println(maxProduct(a));
    }

    static int maxProduct(int[] a)
    {
        int n = a.length;
        Arrays.sort(a);
        return (a[n - 1] - 1) * (a[n - 2] - 1);
    }
}

20

배열에서 두 요소의 최대 곱을 찾는 복잡성 분석

시간 복잡성

O (NlogN), N = 배열의 크기. O (NlogN) 시간이 걸리는 배열을 정렬합니다.

공간 복잡성

O (1), 우리는 일정한 메모리 공간을 사용합니다.

접근 (최적)

위에서 논의했듯이 배열에서 가장 큰 두 요소를 찾아야합니다. 전체 배열을 정렬하여 지나치게 하다 필요한 작업. 따라서 간단한 비교 작업을 통해 배열에서 첫 번째와 두 번째로 큰 요소를 찾는 것이 가장 좋습니다. 따라서 필요한 결과는 다음과 같이 얻을 수 있습니다. (firstMax – 1) * (secondMax – 1).

핀

암호알고리즘

1. firstMax 및 secondMax 두 변수를 XNUMX으로 초기화합니다 (배열의 모든 값이 처음에 업데이트되도록 함).
2. 배열의 시작부터 끝까지 루프를 실행합니다.
3. 모든 요소에 대해 :
   • firstMax보다 큰지 확인하십시오.
     • 만약 사실이라면:
       • secondMax = firstMax 설정
       • firstMax 업데이트 = 현재 요소
     • 그밖에:
       • secondMax보다 큰 경우
         • secondMax 업데이트 = 현재 요소
4. 결과 인쇄

배열 Leetcode 솔루션에서 두 요소의 최대 곱을 찾기위한 알고리즘 구현

C ++ 프로그램

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

int maxProduct(vector <int> &a)
{
    int firstMax = 0 , secondMax = 0 , n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] > firstMax)
        {
            secondMax = firstMax;
            firstMax = a[i];
        }
        else if(a[i] > secondMax)
            secondMax = a[i];

    return (firstMax - 1) * (secondMax - 1);
}

int main()
{
    vector <int> a = {1 , 4 , 5 , 3 , 6 , 4};
    cout << maxProduct(a) << '\n';
}

자바 프로그램

class maximum_product
{
    public static void main(String args[])
    {
        int[] a = {1 , 4 , 5 , 3 , 6 , 4};
        System.out.println(maxProduct(a));
    }

    static int maxProduct(int[] a)
    {
        int firstMax = 0 , secondMax = 0 , n = a.length;
        for(int i = 0 ; i < n ; i++)
            if(a[i] > firstMax)
            {
                secondMax = firstMax;
                firstMax = a[i];
            }
            else if(a[i] > secondMax)
                secondMax = a[i];

        return (firstMax - 1) * (secondMax - 1);
    }
}

20

배열 Leetcode 솔루션에서 두 요소의 최대 곱을 찾는 복잡성 분석

시간 복잡성

O (N), N = 배열의 크기. 간단한 비교 작업을 위해 선형 루프를 실행합니다.

공간 복잡성

O (1), 일정한 메모리가 사용됩니다.