可除數對計數


難度級別
經常問 馬恆達康維瓦 神諭
排列 動態編程 哈希 哈希

可分割對是面試官最喜歡的問題之一。 這個問題足以測試受訪者的問題技能,以及有關數組和哈希圖等主題的知識。

問題陳述:

我們為您提供了以下選擇 不同 正整數。

找到什麼?

使子集中的每個元素遵循一條規則的對數:

  1. 元素(i)%元素(j)= 0
  2. 元素(j)%元素(i)= 0

即,每個元素劃分另一個元素。

方法1

蠻力

用於計數可分割對的Java代碼

class Solution 
{
    public int largestDivisibleSubset(int[] nums) 
    {
    int count=0;
    for(int i=0;i<nums.length;i++)
    {
        for(int j=i+1;j<nums.length;j++)
        {
            if(nums[i]%nums[j]==0 || nums[j]%nums[i]==0)
                count++;
        }
    }
    return count;
    }
}

用於計數可分割對的C ++代碼

class Solution
{
public:
    int largestDivisibleSubset(vector<int>& nums) 
    {
    vector<int>data;
    int count=0;
    for(int i=0;i<nums.size();i++)
    {
        for(int j=i+1;j<nums.size();j++)
        {
            if(nums[i]%nums[j]==0 || nums[j]%nums[i]==0)
                count++;
        }
    }
    return count;
    }
};
[1,2,3,9]
3

時間複雜度= O(n ^ 2)

為什麼呢?

  • 上面的代碼中有兩個循環
  • 首先,在數組上運行的循環捕獲了第一個元素-O(n)
  • 其次,在第一個循環內運行的循環捕獲第二個元素-O(n)
  • 總之,我們得出的時間複雜度為O(n ^ 2)

空間複雜度= O(1)

細微調整

如果要求您返回所有子集中最大的可分割子集,該怎麼辦?

您可能會考慮然後數一些連續對,並逃離面試! 不用擔心,我會以最簡單的方式幫助您並了解解決方案。 首先,我將把方法分解為四個簡單的步驟 DP。

  • 首先對數組排序
  • 對數組進行排序可確保數組的分割出現在數組之前
  • 其次,創建一個數組計數
  • count數組將存儲遇到的一個數的除數
  • 當我們需要最大的子集時,我們循環遍歷 計數 並找到最大的一個
  • 第三,從元素開始,我們添加除數,從而完成子集

一張圖片講一千個單詞,讓我用一張圖片來說明

可分割對簡介
可分割對簡介

Java代碼

class Solution
{
    public List<Integer> largestDivisibleSubset(int[] nums) 
    {
        Arrays.sort(nums);
        List<Integer>lisa=new ArrayList<Integer>();
        if(nums.length==0)
            return lisa;
        int count[]=new int[nums.length];
        int max=Integer.MIN_VALUE;
        Arrays.fill(count,1);
        for(int i=1;i<nums.length;i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(nums[i]%nums[j]==0)
                    count[i]=Math.max(count[i],count[j]+1);
            }
        }
        int maxid=0;
        for(int i=1;i<nums.length;i++)
        {
            if(count[i]>count[maxid])
            {
                maxid = count[i] > count[maxid] ? i : maxid;
            }
        }
        int temp=nums[maxid];
        int curr=count[maxid];
        for(int i=maxid;i>=0;i--)
        {
            System.out.println(nums[i]+" "+temp+" "+count[i]);
            if(temp%nums[i]==0 && count[i]==curr)
            {
                lisa.add(nums[i]);
                temp=nums[i];
                curr--;
            }
        }
        return lisa;
    }
}

C ++代碼

class Solution
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end()); 
        vector<int>lisa;
        if(nums.size()==0)
            return lisa;
        vector<int>count(nums.size(),1);
        for(int i=1;i<nums.size();i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(nums[i]%nums[j]==0)
                    count[i]=maxs(count[i],count[j]+1);
            }
        }
        int maxid=0;
        for(int i=1;i<nums.size();i++)
        {
            if(count[i]>count[maxid])
            {
                maxid = count[i] > count[maxid] ? i : maxid;
            }
        }
        int temp=nums[maxid];
        int curr=count[maxid];
        for(int i=maxid;i>=0;i--)
        {
            if(temp%nums[i]==0 && count[i]==curr)
            {
                lisa.push_back(nums[i]);
                temp=nums[i];
                curr--;
            }
        }
        return lisa;
    }
};

可分割對的複雜度分析

產生的時間複雜度= O(n ^ 2)

我們需要的空間= O(n)

關於如何達到上述時間和空間複雜性的細分

空間複雜度

  • 我們創建兩個額外的空間
  • First-存儲結果的數組
  • 輸入數組的最大數組長度-長度= O(n)
  • 第二個數組,用於存儲子集的長度
  • 數組長度-輸入數組長度= O(n)

時間複雜度

  • 首先,對數組進行排序所花費的時間= O(n log n)
  • 其次,尋找子集所花費的時間= O(n ^ 2)
  • 怎麼樣?
  • 我們運行兩個循環。
  • 外循環考慮了數組中的每個元素
  • 內部循環有助於增加除數的數量
  • 最後,所有這些都會導致O(n ^ 2)+ O(nlogn)的時間複雜度
  • N ^ 2越大,整個問題的時間複雜度O(n ^ 2)