計算數組中存在其產品的對  


難度級別 容易獎學金
經常問 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).

也可以看看
困雨水

空間複雜度: 我們正在維護一個哈希表,用於存儲數組的元素。 所以空間複雜度是 上).

參考