제품이 어레이에 존재하는 쌍 수 계산-TutorialCup

Twitter Facebook 링크드 인 버퍼 레딧 텀블러

배열 문제에 제품이 존재하는 개수 쌍에서 우리는 정렬, 제품 값이 배열에있는 모든 고유 쌍을 계산합니다.

차례

예

입력

A [] = {2, 5, 6, 3, 15}

산출

제품이 어레이에 존재하는 고유 쌍의 수 : 2

쌍 : (2, 3), (5, 3)

무차별 대입 : 제품이 어레이에 존재하는 개수 쌍에 대한 접근 방식 1

모든 쌍을 반복 한 다음 해당 요소가 배열에 존재하는지 확인하십시오. 존재하는 경우 답을 1 씩 증가시킵니다.

암호알고리즘

0으로 변수 ans를 초기화합니다.
0에서 n-1 사이의 I에 대해 루프를 실행합니다.
1. i + 1 ~ n-1 범위에서 j에 대해 루프 실행
  1. 이제 0에서 n-1 사이의 k에 대해 루프를 실행합니다.
    1. A [i] * A [j]가 A [k]와 같으면 ans를 1 씩 증가시키고 루프를 중단합니다.
  2. ans를 인쇄하십시오.

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
void countPairs(vector<int> &A)
{
    int n = A.size();
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                if (A[i] * A[j] == A[k])
                {
                    ans++;
                    break;
                }
            }
        }
    }
    cout << "Number of distinct pairs whose product exists in array is: " << ans << endl;
    return;
}
int main()
{
    vector<int> A = {2, 5, 6, 3, 15, 30};
    countPairs(A);
    return 0;
}

Number of distinct pairs whose product exists in array is: 4

JAVA 프로그램

public class Main
{
    static void countPairs(int[] A)
    {
        int n = A.length;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    if (A[i] * A[j] == A[k])
                    {
                        ans++;
                        break;
                    }
                }
            }
        }
        System.out.print("Number of distinct pairs whose product exists in array is: "+ans);
    }
  public static void main(String[] args) {
    int[] A={2, 5, 6, 3, 15, 30};
    countPairs(A);
  }
}

Number of distinct pairs whose product exists in array is: 4

제품이 어레이에 존재하는 개수 쌍에 대한 복잡성 분석

시간 복잡성 : 우리는 크기가 N 인 세 개의 중첩 루프를 사용하고 있습니다. 따라서 시간 복잡도는 O (N ^ 3).

공간 복잡성 : 추가 공간을 사용하지 않으므로 공간 복잡성은 O (1).

해싱 사용 : 배열에 제품이있는 개수 쌍에 대한 접근 방식 2

주요 아이디어

해시 테이블에 배열의 모든 요소가 있습니다. 그 후, 쌍의 곱이 배열에 존재하면 모든 쌍을 반복하고 답을 1 씩 늘립니다. 해시 테이블에서 일정한 시간에 검색하여 제품이 배열에 있는지 여부를 확인할 수 있습니다.

암호알고리즘

해시 테이블을 선언하십시오.
답을 저장할 변수 ans를 0으로 초기화하십시오.
0에서 n-1 사이의 I에 대해 루프를 실행합니다.
1. j + 1 ~ n-1 범위에서 j에 대해 루프를 실행합니다.
  1. A [i]와 A [j]의 곱이 해시 테이블에 있으면 ans를 1 씩 증가시킵니다.
2. ans를 인쇄하십시오.

예 :

어레이 A [] = {2, 4, 2, 4, 15, 8, 20}의 경우

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

핀

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
void countPairs(vector<int> &A)
{
    int n = A.size();
    unordered_set<int> hash_table;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        hash_table.insert(A[i]);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (hash_table.count(A[i] * A[j]) == 1)
            {
                ans++;
            }
        }
    }
    cout << "Number of distinct pairs whose product exists in array is: " << ans << endl;
    return;
}
int main()
{
    vector<int> A = {2, 4, 2, 4, 15, 30, 8};
    countPairs(A);
    return 0;
}

Number of distinct pairs whose product exists in array is: 7

JAVA 프로그램

import java.util.*; 
public class Main
{
    static void countPairs(int[] A)
    {
        int n = A.length;
        Set<Integer> hash_table=new HashSet<Integer>();
        int ans = 0;
        for(int i=0;i<n;i++)
        {
            hash_table.add(A[i]);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if(hash_table.contains(A[i]*A[j])==true)
                {
                    ans++;
                }
            }
        }
        System.out.print("Number of distinct pairs whose product exists in array are: "+ans);
    }
  public static void main(String[] args) {
    int[] A={2, 4, 2, 4, 15, 30, 8};
    countPairs(A);
  }
}

Number of distinct pairs whose product exists in array are: 7

제품이 어레이에 존재하는 개수 쌍에 대한 복잡성 분석

시간 복잡성 : 크기가 N 인 두 개의 중첩 루프를 사용하고 있습니다. 따라서 시간 복잡도는 O (N ^ 2).

공간 복잡성 : 배열의 요소를 저장하기위한 해시 테이블을 유지하고 있습니다. 따라서 공간 복잡성은 의 위에).

참조

Twitter Facebook 링크드 인 버퍼 레딧 텀블러