주어진 정렬 N 요소 중 A. 작업은 주어진 배열의 두 요소의 곱이되도록 배열에 존재하는 가장 큰 수 S를 찾는 것입니다 (S는 쌍에 포함될 수 없습니다. 또한 쌍은 서로 다른 인덱스에 속해야합니다). 그러한 쌍이 없으면 -1을 인쇄하십시오.
차례
예
입력:
6 10 2 2 4 30 35
출력:
4
무차별 대입 : 배열에서 가장 큰 제품과 쌍 찾기에 대한 접근 방식 1
배열의 모든 숫자 쌍을 가져 와서 해당 제품이 배열에 있는지 여부를 확인할 수 있으며이 모든 유효한 쌍 중에서 가장 높은 제품을 선택합니다.
암호알고리즘
- 감소하지 않는 순서로 배열을 정렬합니다.
- -1로 변수 "ans"를 초기화합니다.
- 0에서 n-1 사이의 I에 대해 루프 실행
- i + 1 ~ n-1 범위에서 j에 대해 루프 실행
- j + 1 ~ n-1 범위에서 k에 대해 루프 실행
- arr [k]가 arr [i] * arr [j]와 같으면 ans = arr [k]의 값을 업데이트하고 루프에서 벗어나십시오.
- j + 1 ~ n-1 범위에서 k에 대해 루프 실행
- i + 1 ~ n-1 범위에서 j에 대해 루프 실행
- 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인지 별도로 확인해야합니다.
암호알고리즘
- 배열을 사용하여 해시 테이블을 만들고 그 안에 모든 배열 요소를 저장합니다.
- 내림차순으로 배열을 정렬합니다.
- 0에서 n-1 사이의 I에 대해 루프 실행
- 범위 2에서 sqrt (arr [i])까지 j에 대해 루프 실행
- j가 arr [i]로 나눌 수 있으면 다른 요소 k = arr [i] / j를 초기화합니다.
- j와 k가 같으면 j의 개수가 1보다 크면 arr [i]가 답이고 두 루프에서 나옵니다.
- j와 k가 같지 않으면 두 요소가 모두 not 배열에 있는지 확인하고, 그렇다면 arr [i]가 답이고 두 루프에서 모두 중단됩니다.
- 범위 2에서 sqrt (arr [i])까지 j에 대해 루프 실행
- 답을 찾았 으면 인쇄하고 그렇지 않으면 인쇄 -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)).
공간 복잡성
해시 테이블을 저장해야 공간 복잡성이 의 위에).
