Wiggle စီရန်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် PayPal က
sorting

တုန်လှုပ်ချောက်ချား Sort!?

ကျွန်တော့်စာဖတ်သူတွေအားလုံးဒီနေ့ပြproblemနာရဲ့နာမည်ကိုအရမ်းရယ်ရတယ်။ သို့သော်၎င်းသည်အလွန်ကောင်းမွန်သောပြproblemနာတစ်ခုဖြစ်ပြီးကျွန်ုပ်တို့၏နားလည်မှုကိုအမျိုးမျိုးသောအယူအဆများကိုစမ်းသပ်သည်။

နောက်ထပ်ရှုပ်ထွေးမှုမရှိဘဲပြstraightနာကိုချက်ချင်းဖြေရှင်းကြပါစို့။

နမူနာ

သင့်မှာ array တစ်ခုရှိတယ်

input: [1,5,1,6,4]

မျှော်လင့်ထားသည့်ရလဒ် - [1,6,4,1,5]

ဘယ်လိုလဲ?

တုန်လှုပ်ချောက်ချားသည် စီရန်:

အဆိုပါ array ရဲ့ element တွေကိုထိုကဲ့သို့သောအမိန့်ပေးလိမ့်မည် arr[0]<arr[1]>arr[2]<arr[3] နှင့်ဒါ wiggle မျိုး၌တည်၏။

ချဉ်းကပ်နည်း

ငါအလွယ်ကူဆုံးကိုရှာဖွေချဉ်းကပ်မှုအပေါ်သွားပါလိမ့်မယ်။ ထည့်သွင်းစဉ်းစားသို့အောက်ပါဥပမာကိုယူပြီး

Array: [1,5,1,1,6,4]

အဲ့ဒီ array ကို copy လုပ်ပြီး sort လုပ်ပါ

မူရင်းနှင့်မိတ္တူပွားခင်းကိုရွေးချယ်ပြီးနောက်ပြသခြင်း
မူရင်းနှင့်မိတ္တူပွားခင်းကိုရွေးချယ်ပြီးနောက်ပြသခြင်း

အပြာရောင် - မူရင်းခင်းကျင်းမှုအနီရောင် - Sorted Copy ခင်း

ခင်းကျင်း၏အရှည်: 6

သေးငယ်သော element များကို copy array မှမူလခင်းကျင်းရန်ထားကြစို့။

ပထမ ဦး ဆုံး set ကိုကူးယူပြီးနောက် sorted နှင့်ကူးယူခင်းကျင်း
ပထမ ဦး ဆုံးအစုကိုကူးယူပြီးနောက် sorted နှင့်ကူးယူခင်းကျင်း

သေးငယ်တဲ့ဒြပ်စင်ကူးယူပြီးနောက်မူရင်းခင်းကျင်း

အခု ပိုကြီးတဲ့ဒြပ်စင်တွေကိုကျန်နေတဲ့နေရာတွေမှာထားကြစို့

ပိုကြီးတဲ့ဒြပ်စင်များကျန်ကြွင်းသောအရပ်သို့နေရာချထား
ပိုကြီးတဲ့ဒြပ်စင်များကျန်ကြွင်းသောအရပ်သို့နေရာချထား

မင်္ဂလာပါ။ အဆိုပါခင်းကျင်း wiggle ခွဲထားပါတယ်!

ကျနော်တို့ကိန်းတွေမကိန်းတွေပါဝင်တဲ့ array အတွက် 'passes' ကိုနည်းနည်းလေးပြောင်းပေးလိမ့်မယ်။

ကြည့်ကြရအောင်။

ကျနော်တို့ကနောက်ဆုံးဒြပ်စင်အစားနောက်ဆုံး element ကနေစတင်လိမ့်မယ်။

ပထမ ဦး ဆုံး pass ပြီးနောက်

ယခုကျွန်ုပ်တို့သည်ပိုကြီးသောဒြပ်စင်ထား၏

ဒြပ်စင်နောက်ဆုံးသောကာလညှိ
ဒြပ်စင်နောက်ဆုံးသောကာလညှိ

A အလားတူပြproblemနာ နားလည်မှုရရန်ကျွန်ုပ်တို့နှင့်အတူစစ်ဆေးနိုင်ပါသည်။

အခုငါတို့နားလည်ပြီ။ ကုဒ်ရအောင်

wiggle မျိုးအတွက် Java Code

class Solution 
{
    int index=0;
    public void assemble(int[] nums,int copy[],int start)
    {
        //The assemble function 
        for(int i=start;i>-1;i=i-2)
        {
            nums[i]=copy[index];
            index++;
        }
    }
    public void wiggleSort(int[] nums) 
    {
        int copy[]=new int[nums.length];
        for(int i=0;i<nums.length;i++)
            copy[i]=nums[i];
        Arrays.sort(copy);
        if(nums.length%2==0)
        {
            assemble(nums,copy,nums.length-2);
            assemble(nums,copy,nums.length-1);
        }
        else
        {
            assemble(nums,copy,nums.length-1);
            assemble(nums,copy,nums.length-2);
        }
    }
}

လှုပ်လှုပ်ရွရွမျိုးများအတွက် C ++ ကုဒ်

class Solution 
{
    public:
    int index=0;
    public:
    void assemble(vector<int>& nums,vector<int>& copy,int start)
    {
        int i=0;
        for(i=start;i>-1;i=i-2)
        {
            nums[i]=copy[index];
            index++;
        }
    }
    public:
    void wiggleSort(vector<int>& nums) 
    {
        vector<int>copy(nums);
        sort(copy.begin(), copy.end());
        if(nums.size()%2==0)
        {
            assemble(nums,copy,nums.size()-2);
            assemble(nums,copy,nums.size()-1);
        }
        else
        {
            assemble(nums,copy,nums.size()-1);
            assemble(nums,copy,nums.size()-2);
        }
    }
};

လှုပ်လှုပ်ရွရွမျိုးများအတွက်ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အထက်ပြProbleနာအတွက်အချိန်ရှုပ်ထွေးခြင်း = အို (n log n)

Wiggle Sorting အတွက် Space Complexity = O (n) နည်းလမ်း

ဘယ်လိုလဲ?

  • အသုံးပြုခဲ့သည့်စစ်ဆင်ရေးအမျိုးအစားသည်ရှုပ်ထွေးသော O (n logn) နှင့်ပေါင်းစပ်ထားသောပေါင်းစည်းခြင်းအမျိုးအစားဖြစ်သည်။
  • တစ်ခုချင်းစီကိုခေါ်ဆိုခအတွက် function ကိုစုဝေးစေ
    • ကျနော်တို့ကအခြား element တွေကိုကျော်ပြေးနှင့်အညီသူတို့ကိုမိတ္တူထဲကနေမူရင်းခင်းကျင်းထား၏
  • ထို့ကြောင့်ကျွန်ုပ်တို့သည် element များနေရာတကျမရောက်မချင်း array ထဲရှိ element တစ်ခုစီကိုဖြတ်သန်းသွားသည်
  • ခင်းကျင်းခြင်းသို့ပြောင်းခြင်းသည်အချိန် (O) ကိုရှုပ်ထွေးစေသည်။
  • သို့သော် sort လုပ်ငန်းစဉ်သည်ဤကိစ္စတွင်ပိုမိုရှုပ်ထွေးပြီးအချိန်ရှုပ်ထွေးမှုကို O သို့ယူဆောင်လာသည် (n logn)
  • ကျနော်တို့ element တွေကိုအတူ Copy ကူးခင်းကျင်းဖန်တီးအဖြစ်။ အာကာသရှုပ်ထွေး O (n) ဆိုလိုသည်မှာ linear အပေါ်သုည