Array-da ən yaxşı məhsul ilə cüt tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Samsung
Geyim HashingBaxılıb 33

Verilmiş bir array N elementdən A. Tapşırıq, verilmiş bir sıra iki elementinin məhsulu olacağı şəkildə massivdə mövcud olan ən böyük S sayını tapmaqdır (S cütə daxil edilə bilməz. Həm də cütlük fərqli indekslərdən olmalıdır). Əgər belə bir cüt yoxdursa, onda -1 yazdırın.

misal

Input:

6 10 2 2 4 30 35

Çıxış:

4

Kobud qüvvə: Array-da ən yaxşı məhsulla cüt tapmaq üçün yanaşma 1

Dizidəki hər cüt cütü götürə bilərik və məhsulun massivdə olub olmadığını yoxlaya bilərik və bütün bu etibarlı cütlər arasında ən yüksək məhsulu seçəcəyik.

Alqoritm

  1. Dizini azalan qaydada çeşidləyin.
  2. Dəyişən “ans” ı -1 ilə başlayın.
  3. 0-dan n-1 aralığında I üçün bir döngə çalıştırın
    • J üçün i + 1 - n-1 aralığında bir döngə çalıştırın
      • J + 1-dən n-1 aralığında k üçün bir döngə işlədin
        • Arr [k] arr [i] * arr [j] -ə bərabərdirsə, ans = arr [k] dəyərini yeniləyin və döngədən çıxın.
  4. Ans çap et.

Həyata keçirilməsi

Dizidəki ən böyük məhsula sahib cüt tapmaq üçün C ++ proqramı

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr.begin(),arr.end());
    int ans=-1;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int k=j+1;k<n;k++)
            {
                if(arr[k]==arr[i]*arr[j])
                {
                    ans=arr[k];
                    break;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
6
10 2 2 4 30 35
4

Dizidəki ən böyük məhsula sahib cüt tapmaq üçün JAVA proqramı

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i]=sc.nextInt();
        }
        Arrays.sort(arr);
        int ans=-1;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    if(arr[k]==arr[i]*arr[j])
                    {
                        ans=arr[k];
                        break;
                    }
                }
            }
        }
    System.out.println(ans);
  }
}


9
35 7 5 8 2 2 56 3 1
56

Dizidəki ən böyük məhsula sahib cüt tapmaq üçün mürəkkəblik analizi

Zaman mürəkkəbliyi

N ölçülü 3 iç içə döngə işlədirik, ümumi zaman mürəkkəbliyimizdir O (N ^ 3).

Kosmik Mürəkkəblik

Yalnız 1 əlavə dəyişən götürdük, buna görə daimi bir yer mürəkkəbliyimiz var O (1).

Hashingdən istifadə: Array-da ən yaxşı məhsul ilə cüt tapmaq üçün 2 yanaşma

Əsas fikir

bütün element elementlərini bir elementin O (1) vaxtında olub olmadığını yoxlamaq üçün bir hash cədvəlində saxlaya bilərik. İndi hər bir elementi, məhsulu elementə bərabər olan bir cüt hissəsinin massivdə olub olmadığını yoxlaya bilərik.

Ayrıca, elementin aralığı 0 ilə 10 ^ 5 arasındadır, buna görə sadəcə üçün bir sıra istifadə edə bilərik sükut masa.

Cari elementin mükəmməl bir kvadrat və ya 1-ə bərabər olub olmadığını ayrı-ayrılıqda yoxlamalıyıq.

Alqoritm

  1. Bir sıra istifadə edərək bir hash masa yaradın və bütün array elementlərini içərisində saxlayın.
  2. Dizini azalan sırada sıralayın.
  3. 0-dan n-1 aralığında I üçün bir döngə çalıştırın
    • J üçün sqrt (arr [i]) aralığında 2 üçün bir döngə işlədin
      1. J arr [i] ilə bölünürsə, başqa bir element k = arr [i] / j başlanğıc edin.
      2. J və k bərabərdirsə, j sayı 1-dən çox olarsa arr [i] cavabdır və hər iki döngədən çıxır.
      3. J və k bərabər deyilsə, not elementində hər iki elementin olub olmadığını yoxlayın, bəli əgər arr [i] cavabdır və hər iki döngədən qopun.
  1. Cavab tapmışıqsa, başqa bir şəkildə çap et -1.

Məsələn:

Giriş massivi = {10, 2, 2, 4, 30, 35}

Sonra hash cədvəli belə görünür:

Sağ sütunda ədədi, sağ sütunda isə onların tezliyini massivdə göstərir.

Array-da ən yaxşı məhsul ilə cüt tapınPin

Həyata keçirilməsi

Dizidəki ən böyük məhsula sahib cüt tapmaq üçün C ++ proqramı

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> m(100001,0);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        m[a[i]]++;
    }
    sort(a.begin(), a.end(),greater<int>());
    bool flag = false;
    for (int i = 0; i<n; i++)
    {
        if (a[i] == 1)
        {
            if (m[a[i]] >= 3)
            {
                cout << a[i] << endl;
                flag = true;
                break;
            }
            else
            {
                continue;
            }
        }
        for (int divisor_1 = 2; divisor_1 * divisor_1 <= a[i]; divisor_1++)
        {
            if (a[i] % divisor_1 == 0)
            {
                int divisor_2 = a[i] / divisor_1;
                if (divisor_1 == divisor_2)
                {
                    if (m[divisor_1] > 1)
                    {
                        cout << a[i] << endl;
                        flag = true;
                        break;
                    }
                }
                else
                {
                    if ((m[divisor_1]>0) and (m[divisor_2]>0))
                    {
                        cout << a[i] << endl;
                        flag = true;
                        break;
                    }
                }
            }
        }
        if (flag)
        {
            break;
        }
    }
    if (flag == false)
    {
        cout << "-1" << endl;
    }
    return 0;
} 
11
22 72 9 8 11 33 123 21 45 10 5
72

Dizidəki ən böyük məhsula sahib cüt tapmaq üçün Java proqramı

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a=new int[n];
        int[] m=new int[100001];
        for(int i=0;i<n;i++)
        {
            a[i]=sc.nextInt();
            m[a[i]]++;
        }
        Arrays.sort(a);
        boolean flag = false;
        for (int i = n-1; i>=0; i--)
        {
            if (a[i] == 1)
            {
                if (m[a[i]] >= 3)
                {
                    System.out.println(a[i]);
                    flag = true;
                    break;
                }
                else
                {
                    continue;
                }
            }
            for (int divisor_1 = 2; divisor_1 * divisor_1 <= a[i]; divisor_1++)
            {
                if (a[i] % divisor_1 == 0)
                {
                    int divisor_2 = a[i] / divisor_1;
                    if (divisor_1 == divisor_2)
                    {
                        if (m[divisor_1] > 1)
                        {
                            System.out.println(a[i]);
                            flag = true;
                            break;
                        }
                    }
                    else
                    {
                        if ((m[divisor_1]>0) && (m[divisor_2]>0))
                        {
                            System.out.println(a[i]);
                            flag = true;
                            break;
                        }
                    }
                }
            }
            if (flag)
            {
                break;
            }
        }
        if (flag == false)
        {
            System.out.println("-1");
        }
    
  }
}
11
22 72 9 8 11 33 123 21 45 10 5
72

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

Ən pis vəziyyətdə bütün massivi təkrarlayırıq və hər element üçün sqrt (N) üçün bir döngə işlədirik. Beləliklə, ümumi vaxt mürəkkəbliyi O (N ^ sqrt (N)).

Kosmik mürəkkəblik

Məkan mürəkkəbliyi olduğu üçün bir hash masası saxlamalıyıq O (N).

References

Translate »