Duplicate II Leetcode Solution ပါ ၀ င်သည်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Facebook က Google
အခင်းအကျင်း တားဆီးခြင်း လျှော Window

ပြProbleနာဖော်ပြချက်

ဤပြproblemနာတွင်ကျွန်ုပ်တို့အားပေးထားသည် အခင်းအကျင်း အနည်းဆုံးအကွာအဝေးမှာရှိတဲ့ထပ်ပွားပစ္စည်းတစ်ခုခုရှိသလားဆိုတာကျွန်တော်တို့စစ်ဆေးရမယ် k တစ်ဦးချင်းစီကတခြားရန်။
ဆိုလိုသည်မှာထိုဒြပ်စင်နှစ်ခု၏အညွှန်းကိန်းများအကြားခြားနားချက်သည် k နှင့်ညီသည်ထက်နည်းရမည်။
သို့မဟုတျ,  nums [i] == nums [ည] နှင့် ABS (ij) <= ။

နမူနာ

nums = [1,2,3,1], k = 3
true

ရှင်းလင်းချက်:

အညွှန်းကိန်း 0 နှင့် 3 မှာဒြပ်စင်အတူတူဖြစ်ပြီး, 3 - 0 <= k ။

nums = [1,2,3,1,2,3], k = 2
false

ချဉ်းကပ်နည်း 1 (Brute Force)

Brute Force ချဉ်းကပ်မှုအကြောင်းပြောရင် loops နှစ်ခုသုံးပြီးပရိုဂရမ်ကိုရိုးရှင်းစွာအကောင်အထည်ဖော်ပြီး element တစ်ခုချင်းစီရှိ၊ မရှိရှိမရှိအကွာအဝေး k ကိုအကွာအဝေးအထိစစ်ဆေးနိုင်သည်။
အကယ်၍ element တစ်ခုသည် current element နှင့်ထပ်တူကျပါကကျွန်ုပ်တို့သည် true သို့ပြန်သွားပါမည်။

algorithm

  1. ဒြပ်စင်တိုင်းအတွက်ကွင်းဆက်တစ်ခု run ပါ nums [i] ပေးထားသောခင်းကျင်း၏။
  2. ဒီ loop အတွင်း for for loop ကိုသုံးပြီး element အားလုံးကိုဖြတ်သန်းပါ ည = ဈ + 1 သို့ ည = ဈ + k နှင့်၎င်း၏တန်ဖိုးကိုနှိုင်းယှဉ် nums [i] ။
    • If nums [ည] == nums [i] ပြီးရင်ပြန်သွားပါ။ ကျနော်တို့ကဒြပ်စင်တွေ့ပြီအဖြစ်။
  3. နောက်ဆုံးအဘယ်သူမျှမထပ်ဒြပ်စင်မတွေ့သောအခါ function ကိုမထွက်ခင် false ကိုပြန်သွားပါ။

အဘို့အအကောင်အထည်ဖော် Duplicate II ကို Leetcode ဖြေရှင်းချက်

C ++ အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    for(int i=0;i<nums.size();i++)
        for(int j=i+1;j<nums.size() && j<=i+k;j++)
        {
            if(nums[j]==nums[i])
                return true;
        }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

Java အစီအစဉ်

class Rextester{
    
    public static boolean containsNearbyDuplicate(int[] nums, int k) 
    {
        for(int i=0;i<nums.length;i++)
            for(int j=i+1;j<nums.length && j<=i+k;j++)
            {
                if(nums[j]==nums[i])
                    return true;
            }

        return false;

    }
    
    public static void main(String args[])
    {
       	int[] nums={1,2,3,1};
        int k=3;
        System.out.println(containsNearbyDuplicate(nums,k) );
    }
}
true

အဘို့အရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာခြင်း Duplicate II ကို Leetcode ဖြေရှင်းချက်ပါရှိသည်

အချိန်ရှုပ်ထွေး

အို (n * min (,, n)): ကျွန်ုပ်တို့သည် array ၏ element အားလုံးအတွက် min (k, n) element များကိုဖြတ်သန်းနေသည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုအို (n * မိ (,၊ n)) ဖြစ်လိမ့်မည်။

အာကာသရှုပ်ထွေးမှု 

အို (၁) စဉ်ဆက်မပြတ်အာကာသ။

ချဉ်းကပ်မှု ၂ (လျှော ၀ င်းဒိုး)

ကျွန်ုပ်တို့တွေ့မြင်ရသည့်အတိုင်းကျွန်ုပ်တို့သည်၎င်း၏အချိန်ရှုပ်ထွေးမှုကိုတိုးပွားစေသော array ၏ဒြပ်စင်များသို့တစ်ကြိမ်ထက်မကသွားနေကြသည်။ ကျွန်ုပ်တို့သည် O (n) သို့အချိန်ကိုလျှော့ချရန် element တစ်ခုစီသို့တစ်ကြိမ်သာသွားသင့်သည်။

၎င်းအတွက်ကျွန်ုပ်တို့လုပ်နိုင်သည်မှာကျွန်ုပ်တို့သည်ယခင်၏လျှော ၀ င်းဒိုးကိုသိမ်းထားနိုင်သည် k Hash Set ကိုအသုံးပြုပြီး element များကျွန်ုပ်တို့သည် array ထဲရှိမည်သည့် element ကိုမဆိုကျွန်ုပ်တို့သွားတိုင်းအချိန်တိုင်းတွင်ရှိသည်။ ဤသို့ပြုလုပ်ခြင်းအားဖြင့်ကျွန်ုပ်တို့သည်ယခင် k element များ၏အစုံမှကျွန်ုပ်တို့အလွယ်တကူစစ်ဆေးနိုင်သည်၊ အစုအတွင်း၌ကျွန်ုပ်တို့လည်ပတ်နေသောလက်ရှိဒြပ်စင်နှင့်တူညီသောဒြပ်စင်တစ်ခုရှိလျှင်၎င်းကိုအလွယ်တကူစစ်ဆေးနိုင်သည်။ set ကိုတွေ့ပြီဆိုရင်အဲ့ဒီအချိန်မှာ true ပြန်ရမယ်။ အခြားအရာများမှာမူလက်ရှိ element ကို set ထဲထည့်ပြီးနောက်ဆုံးမှလာရောက်လည်ပတ်သော element ကို set မှဖယ်ရှားပေးပါလိမ့်မည် k ကျွန်တော်တို့ရဲ့အစုအတွက်ယခင်ဒြပ်စင်။

အောက်ကပုံမှာဥပမာတစ်ခုကိုကြည့်ရအောင်။

Duplicate II Leetcode Solution ပါ ၀ င်သည်

algorithm

  1. တစ်ဦး Create Hash သတ်မှတ်မည် သိုလှောင်ဘို့ k ယခင်ဒြပ်စင်။
  2. ပေးထားသောခင်းကျင်းမှုတစ်ခုမှ element တစ်ခုစီ၏နံပါတ်များအတွက်လမ်းကြောင်း။
    • hash အစုံတွင် nums [i] ပါမပါစစ်ဆေးပါ။ အကယ်၍ nums [i] သည် set ထဲတွင်ရှိသည်ဆိုလျှင် (ဆိုလိုသည်မှာ duplicate element သည်ညီမျှခြင်းထက်မဝေးသောအကွာအဝေးတွင်ရှိသည် k ), ထို့နောက်စစ်မှန်တဲ့ပြန်လာ။ ကျန်အစုများအတွက် nums [i] ထည့်ပါ။
    • set ၏အရွယ်အစား k ထက်သာ။ ကြီးမြတ်ဖြစ်လာလျှင်, အစုထဲကနေနောက်ဆုံးသွားရောက်ခဲ့ပြီး element ကို (nums [ik]) ဖယ်ရှားပါ။
  3. နောက်ဆုံးအဘယ်သူမျှမထပ်ဒြပ်စင်မတွေ့သောအခါ function ကိုမထွက်ခင် false ကိုပြန်သွားပါ။

အဘို့အအကောင်အထည်ဖော် Duplicate II ကို Leetcode ဖြေရှင်းချက်

C ++ အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);

        if(set.size()>k)
            set.erase(nums[i-k]);
    }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

Java အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);

        if(set.size()>k)
            set.erase(nums[i-k]);
    }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

အဘို့အရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာခြင်း Duplicate II ကို Leetcode ဖြေရှင်းချက်ပါရှိသည်

အချိန်ရှုပ်ထွေး

အို ()) ကျွန်ုပ်တို့သည် element တစ်ခုစီကိုတစ်ကြိမ်သာ သွားရောက်၍ element တစ်ခုထည့်ခြင်းနှင့် element တစ်ခုကိုဖယ်ရှားခြင်းသည် hash set အချိန်တွင်ရှုပ်ထွေးသောအချိန်တွင် O (n) သို့လျှော့ချသည်ဟုယူဆသောကြောင့်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု 

အို (မိ (,၊ ))) ကျွန်ုပ်တို့သည် hash set တွင် k element များကို max တွင်သိုလှောင်ထားသည်။ k> n လျှင်သာဒြပ်စင် max ကိုမှာအစု၌သိမ်းဆည်းထားလိမ့်မည်။