Երկու տարրերի առավելագույն արտադրանքը զանգվածում Leetcode լուծման մեջ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Samsung
Դասավորություն

«Rayանգվածի երկու տարրերի առավելագույն արտադրյալ» խնդրում մեր նպատակն է գտնել երկու ցուցանիշ i և j ամբողջ թվերի տվյալ զանգվածում a, այնպես, որ արտադրանքը (a [i] - 1) * (a [j] - 1) առավելագույն լինի: Rayանգվածն ունի առնվազն 2 տարր և բոլոր տարրերը դրական են: Խնդիրը, որ պահանջվող արտադրանքը տեղավորվում է ամբողջ թվային տիրույթում: Մենք պետք է տպենք (a [i] - 1) * (a [j] - 1) արժեքը օպտիմալի համար i & j.

Օրինակ

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

բացատրություն

Ակնհայտ է, որ 6-ը և 5-ը ամենամեծ և երկրորդ մեծ թվերն են: Այսպիսով, արտադրանք = (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)

Gorանգվածում երկու տարրերի առավելագույն արտադրանքը գտնելու ալգորիթմի ներդրում

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';
}

Java ծրագիր

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

Rayանգվածի երկու տարրերի առավելագույն արտադրանքը գտնելու բարդության վերլուծություն

Timeամանակի բարդություն

O (NlogN), N = զանգվածի չափը: Մենք տեսակավորում ենք զանգվածը, որը O (NlogN) ժամանակ է պահանջում:

Տիեզերական բարդություն

Ո (1), քանի որ մենք օգտագործում ենք հիշողության անընդհատ տարածություն:

Մոտեցում (օպտիմալ)

Ինչպես մենք վերը քննարկեցինք, մենք պետք է գտնենք զանգվածի երկու մեծագույն տարրերը: Տեսակավորելով ամբողջ զանգվածը ՝ մենք չափազանցել պահանջվող աշխատանքը: Այսպիսով, օպտիմալ է զանգվածում գտնել առաջին և երկրորդ ամենամեծ տարրը `համեմատելով պարզ գործողությունները: Այսպիսով, պահանջվող արդյունքը կարելի է ստանալ, ինչպես (firstMax - 1) * (secondMax - 1).

Երկու տարրերի առավելագույն արտադրանքը զանգվածում Leetcode լուծման մեջ

Ալգորիթմ

  1. Նախապատկերացրեք երկու փոփոխական `firstMax- ը և secondMax- ը որպես զրո (այնպես, որ զանգվածի ցանկացած արժեք դրանք թարմացնի ներսից):
  2. Runանգի մեկնարկից մինչև դրա վերջը գործարկեք մի օղակ:
  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';
}

Java ծրագիր

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

Eleանգվածի Leetcode լուծույթում երկու տարրերի առավելագույն արտադրանքը գտնելու բարդության վերլուծություն

Timeամանակի բարդություն

O (N), N = Rayանգվածի չափը: Մենք իրականացնում ենք գծային օղակ ՝ համեմատության պարզ գործողությունների համար:

Տիեզերական բարդություն

O (1), քանի որ օգտագործվում է մշտական ​​հիշողություն: