배열에서 가장 큰 제품과 쌍 찾기

난이도 쉽게
자주 묻는 질문 삼성
배열 해싱조회수 33

주어진 정렬 N 요소 중 A. 작업은 주어진 배열의 두 요소의 곱이되도록 배열에 존재하는 가장 큰 수 S를 찾는 것입니다 (S는 쌍에 포함될 수 없습니다. 또한 쌍은 서로 다른 인덱스에 속해야합니다). 그러한 쌍이 없으면 -1을 인쇄하십시오.

입력:

6 10 2 2 4 30 35

출력:

4

무차별 대입 : 배열에서 가장 큰 제품과 쌍 찾기에 대한 접근 방식 1

배열의 모든 숫자 쌍을 가져 와서 해당 제품이 배열에 있는지 여부를 확인할 수 있으며이 모든 유효한 쌍 중에서 가장 높은 제품을 선택합니다.

암호알고리즘

  1. 감소하지 않는 순서로 배열을 정렬합니다.
  2. -1로 변수 "ans"를 초기화합니다.
  3. 0에서 n-1 사이의 I에 대해 루프 실행
    • i + 1 ~ n-1 범위에서 j에 대해 루프 실행
      • j + 1 ~ n-1 범위에서 k에 대해 루프 실행
        • arr [k]가 arr [i] * arr [j]와 같으면 ans = arr [k]의 값을 업데이트하고 루프에서 벗어나십시오.
  4. ans를 인쇄하십시오.

실시

배열에서 가장 큰 제품과 쌍을 찾기위한 C ++ 프로그램

#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

배열에서 가장 큰 제품과 쌍을 찾기위한 JAVA 프로그램

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

배열에서 가장 큰 제품과 쌍을 찾기위한 복잡성 분석

시간 복잡성

크기가 N 인 3 개의 중첩 루프를 실행할 때 총 시간 복잡도는 다음과 같습니다. O (N ^ 3).

공간 복잡성

우리는 하나의 추가 변수 만 취 했으므로 일정한 공간 복잡성을가집니다. O (1).

해싱 사용 : 배열에서 가장 큰 제품과 쌍을 찾기위한 방법 2

주요 아이디어

모든 배열 요소를 해시 테이블에 저장하여 요소가 O (1) 시간에 존재하는지 여부를 확인할 수 있습니다. 이제 우리는 곱이 요소와 동일한 제수 쌍이 배열에 있는지 여부를 각 요소에 대해 확인할 수 있습니다.

또한 요소의 범위는 0에서 10 ^ 5까지이므로 간단히 배열을 사용할 수 있습니다. 해시 테이블.

그리고 현재 요소가 완전 제곱인지 1인지 별도로 확인해야합니다.

암호알고리즘

  1. 배열을 사용하여 해시 테이블을 만들고 그 안에 모든 배열 요소를 저장합니다.
  2. 내림차순으로 배열을 정렬합니다.
  3. 0에서 n-1 사이의 I에 대해 루프 실행
    • 범위 2에서 sqrt (arr [i])까지 j에 대해 루프 실행
      1. j가 arr [i]로 나눌 수 있으면 다른 요소 k = arr [i] / j를 초기화합니다.
      2. j와 k가 같으면 j의 개수가 1보다 크면 arr [i]가 답이고 두 루프에서 나옵니다.
      3. j와 k가 같지 않으면 두 요소가 모두 not 배열에 있는지 확인하고, 그렇다면 arr [i]가 답이고 두 루프에서 모두 중단됩니다.
  1. 답을 찾았 으면 인쇄하고 그렇지 않으면 인쇄 -1.

예를 들어 :

입력 배열 = {10, 2, 2, 4, 30, 35}

그러면 해시 테이블은 다음과 같습니다.

오른쪽 열에는 숫자가 표시되고 오른쪽 열에는 배열의 빈도가 표시됩니다.

배열에서 가장 큰 제품과 쌍 찾기

실시

배열에서 가장 큰 제품과 쌍을 찾기위한 C ++ 프로그램

#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

배열에서 가장 큰 제품과 쌍을 찾기위한 Java 프로그램

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

복잡성 분석

시간 복잡성

최악의 경우 전체 배열을 반복하고 각 요소에 대해 sqrt (N)에 대한 루프를 실행합니다. 따라서 총 시간 복잡성은 O (N ^ sqrt (N)).

공간 복잡성

해시 테이블을 저장해야 공간 복잡성이 의 위에).

참조

Translate »