计算数组中存在其产品的对


难度级别 易得奖学金
经常问 ol石 亚马逊 贝莱德 月蛙实验室 奥拉出租车 Snapchat Xome
排列 哈希

在其产品存在数组问题的计数对中,我们给出了 排列,计算数组中存在乘积值的所有不重复对。

使用案列

输入

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

输出

其乘积存在于数组中的不重复对的数量为:2

对为:(2,3),(5,3)

蛮力:针对阵列中存在产品的计数对的方法1

遍历所有对,然后检查该元素是否存在于数组中。 如果存在,则将答案增加1。

算法

  1. 用0初始化变量ans。
  2. 在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. 打印答案。

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。我们可以通过在固定时间内在哈希表中搜索来检查数组中是否存在乘积。

算法

  1. 声明一个哈希表。
  2. 用0初始化变量ans,它将存储答案。
  3. 对0到n-1的I进行循环。
    1. 对j在j + 1到n-1范围内运行一个循环;
      1. 如果哈希表中存在A [i]和A [j]的乘积,则将ans递增1。
    2. 打印答案。

例如:

对于数组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).

空间复杂度: 我们正在维护一个哈希表,用于存储数组的元素。 所以空间复杂度是 上).

參考資料