شمارش جفتهای قابل تقسیم


سطح دشواری متوسط
اغلب در ماهیندرا کامویوا وحی
صف برنامه نویسی پویا مخلوط هشی کردن

جفت های قابل تقسیم یکی از مشکلات مورد علاقه مصاحبه گر است. این مسئله برای آزمایش مهارتهای مسئله مصاحبه شوندگان همراه با دانش در موضوعاتی مانند آرایه ها و نقشه های هش به اندازه کافی خوب است.

بیان مسأله:

ما انتخاب شده است متمایز اعداد صحیح مثبت

چه چیزی پیدا کنیم؟

تعداد جفت ها به گونه ای است که هر عنصر در زیرمجموعه از یک قانون پیروی می کند:

  1. عنصر (i)٪ عنصر (j) = 0
  2. عنصر (j)٪ عنصر (i) = 0

یعنی هر عنصر عنصر دیگر را تقسیم می کند.

رویکرد -1

نیروی بیرحمانه

کد جاوا برای شمارش زوج های قابل تقسیم

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

  • ابتدا آرایه را مرتب کنید
  • مرتب سازی آرایه اطمینان حاصل می کند که تقسیمات آرایه قبل از آن ظاهر می شود
  • در مرحله دوم ، یک تعداد آرایه ایجاد کنید
  • آرایه شمارش تعداد تقسیم کننده های عددی را پیدا می کند که ذخیره می شود
  • همانطور که به بزرگترین زیرمجموعه نیاز داریم ، حلقه را از طریق شمارش و یکی را با بزرگترین پیدا کنید
  • ثالثاً از عنصر ، مقسوم علیه را اضافه می کنیم بنابراین زیرمجموعه را کامل می کنیم

همانطور که یک تصویر واحد برای هزار کلمه صحبت می کند ، بگذارید همین را با یک تصویر نشان دهم

خلاصه داستان جفتهای قابل تقسیم
خلاصه داستان جفتهای قابل تقسیم

کد جاوا

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)

تجزیه و تحلیل چگونگی رسیدن به پیچیدگیهای زمانی و مکانی گفته شده

پیچیدگی فضا

  • ما دو فضای اضافی ایجاد می کنیم
  • ابتدا آرایه ای برای ذخیره نتایج
  • حداکثر طول آرایه - طول آرایه ورودی = O (n)
  • Second-a array برای ذخیره طول زیرمجموعه ها
  • طول آرایه - طول آرایه ورودی = O (n)

پیچیدگی زمان

  • در ابتدا زمان مرتب سازی برای آرایه = O (n log n)
  • ثانیا ، زمان صرف شده برای یافتن زیرمجموعه ها = O (n ^ 2)
  • چگونه؟
  • ما دو حلقه را اجرا می کنیم.
  • حلقه بیرونی هر عنصر از آرایه را در نظر می گیرد
  • حلقه داخلی به جمع شدن تقسیم کنندگان کمک می کند
  • سرانجام ، همه اینها منجر به پیچیدگی زمانی O (n ^ 2) + O (nlogn) می شود
  • بزرگتر بودن N ^ 2 باعث پیچیدگی زمان کل مسئله O می شود (n ^ 2)