ផលិតផលអតិបរិមានៃធាតុពីរនៅក្នុងដំណោះស្រាយអារេឡេតូកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Samsung
អារេ

នៅក្នុងបញ្ហា“ ផលិតផលអតិបរិមានៃធាតុពីរក្នុងអារេ” គោលដៅរបស់យើងគឺស្វែងរកសន្ទស្សន៍ពីរ i និង j នៅក្នុងអារេនៃចំនួនគត់ a, ដូចជាថាផលិតផល (a [i] - 1) * (a [ច] - ១) គឺអតិបរមា។ អារេមានយ៉ាងហោចណាស់ 1 ធាតុហើយធាតុទាំងអស់គឺវិជ្ជមាន។ បញ្ហាដែលផលិតផលត្រូវការសមនឹងជួរចំនួនគត់។ យើងត្រូវបោះពុម្ពតម្លៃនៃ (a [i] - 2) * (a [j] - 1) ដើម្បីទទួលបានលទ្ធផលល្អ i & j.

តារាង​មាតិកា

ឧទាហរណ៍

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

ការពន្យល់

ច្បាស់ណាស់លេខ ៦ និង ៥ គឺជាលេខធំជាងគេនិងលេខ ២ ។ ដូច្នេះ, ផលិតផល = (a [i] - ១) * (a [ជ] - ១) = ២០ ។

វិធីសាស្រ្ត (តម្រៀប)

ផលិតផល: (a [ខ្ញុំ] - ១) * (a [ច] - ១) នឹងមានអតិបរិមានៅពេលដែល a [i] និង a [j] គឺជាធាតុធំជាងគេពីរនៅក្នុងអារេ។ ជំនួសឱ្យការស្វែងរកសូចនាករពីរដែលខ្ញុំនិង 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) ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១)ដូចដែលយើងប្រើទំហំចងចាំថេរ។

វិធីសាស្រ្ត (ប្រសើរបំផុត)

ដូចដែលយើងបានពិភាក្សាខាងលើយើងត្រូវរកធាតុធំបំផុតពីរនៅក្នុងអារេ។ ដោយការតម្រៀបអារេទាំងមូលយើង ធ្វើលើស ការងារដែលត្រូវការ។ ដូច្នេះវាល្អប្រសើរបំផុតក្នុងការស្វែងរកធាតុធំជាងគេទីមួយនិងទីពីរនៅក្នុងអារេដោយប្រៀបធៀបប្រតិបត្តិការសាមញ្ញ។ ដូច្នេះលទ្ធផលដែលត្រូវការអាចទទួលបានដូច (ម៉ាយទី ១ - ១) * (វិនាទីទី ១ - ១).

ផលិតផលអតិបរិមានៃធាតុពីរនៅក្នុងដំណោះស្រាយអារេឡេតូកូដ

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើមអថេរពីរ: ទីមួយម៉ាយនិងម៉ាយទីពីរជាសូន្យ (ដូច្នេះតម្លៃណាមួយនៅក្នុងអារេធ្វើឱ្យទាន់សម័យដល់ពួកគេ) ។
  2. ដំណើរការរង្វិលជុំពីការចាប់ផ្តើមនៃអារេរហូតដល់ចុងបញ្ចប់របស់វា។
  3. សម្រាប់ធាតុទាំងអស់៖
    • ពិនិត្យមើលថាតើវាធំជាង FirstMax៖
      • បើពិត៖
        • កំណត់ secondMax = firstMax
        • ធ្វើឱ្យទាន់សម័យដំបូងម៉ាអេម = ធាតុបច្ចុប្បន្ន
      • ផ្សេងទៀត៖
        • ប្រសិនបើវាធំជាងម៉ាយទីពីរម៉ាយ
          • ធ្វើឱ្យទាន់សម័យទីពីរម៉ាសា = ធាតុបច្ចុប្បន្ន
  4. បោះពុម្ពលទ្ធផល

ការអនុវត្តក្បួនដោះស្រាយដើម្បីរកផលិតផលអតិបរិមានៃធាតុពីរក្នុងដំណោះស្រាយអារេឡេហ្សិច

កម្មវិធី 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

ការវិភាគស្មុគស្មាញនៃការស្វែងរកផលិតផលអតិបរិមានៃធាតុពីរនៅក្នុងដំណោះស្រាយអារេឡេហ្សកូដ

ស្មុគស្មាញពេលវេលា

O (N), N = ទំហំនៃអារេ។ យើងដំណើរការរង្វិលជុំលីនេអ៊ែរសម្រាប់ប្រតិបត្តិការប្រៀបធៀបសាមញ្ញ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ដូចការចងចាំថេរត្រូវបានប្រើ។