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


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Cadence အိန္ဒိယ ကို eBay GE Healthcare ကရာတေး Quora SAP Labs ရင်ပြင်
အခင်းအကျင်း တပ်မက်သော sorting

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

မင်းမှာတစ်ခုရှိတယ်ဆိုပါစို့ ကိန်း အခင်းအကျင်း။ ဒီခင်းကျင်းမှုကိုကိန်းဂဏန်းတစ်ခုအနေဖြင့်ကုသသင့်သည် မြို့ပတ်ရထားခင်းကျင်း။ Array တစ်ခု၏နောက်ဆုံးတန်ဖိုးသည်ပထမ array နှင့်ချိတ်ဆက်လိမ့်မည်n ⇒ a1 ။ ပြ “နာ က“ Circular array အတွင်းအဆက်မပြတ်ကွဲပြားမှုများ၏ပေါင်းလဒ်ကိုတိုးမြှင့်” သည်ဆက်တိုက်ဒြပ်စင်တစ်ခုအကြားခြားနားချက်၏အများဆုံးပေါင်းလဒ်ကိုရှာဖွေရန်တောင်းဆိုသည်။ ဒါကြောင့်သင်ကဆက်တိုက်ဒြပ်စင်အကြားခြားနားချက်ကိုရှာဖွေရန်ရှိသည်။ နံပါတ်စဉ်များကိုပြန်လည်စီစဉ်ရန်သင့်အားခွင့်ပြုသည်။ သူတို့ရဲ့ကွဲပြားခြားနားမှုများ၏ပေါင်းလဒ်အများဆုံးဖြစ်သင့်ကြောင်းထိုကဲ့သို့သော။

အများဆုံးပေါင်းလဒ် = | a1 - a2 | + | a3 - a4 | + | ကn-1 - ကn | + | ကn - a1 |

နမူနာ

arr[]={9, 8, 4, 2}
22

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

ပေးထားတဲ့ခင်းကျင်းမှုကို 9, 2, 8, 4 အဖြစ်စီစဉ်နိုင်ပါတယ်

| 9 - 2 | + | 2 - 8 | + | 8 - 4 | + | 4 - 9 | = ၂၂

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

algorithm

1. Set a variable output to 0.
2. Sort the given array.
3. Traverse up to n/2 length of the array(n is the length of the array).
    1. Sum up the value of output and array’s last values and store it to sum.
    2. Get the difference of output and twice of array’s starting value and store it to the output.
4. Return the value of output.

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

ထည့်သွင်းစဥ်းစားပါက အခင်းအကျင်း of ကိန်း။ အဆိုပါခင်းကျင်းတဲ့အဖြစ်ကုသရပါမည် မြို့ပတ်ရထားခင်းကျင်း အရာကိုတိုက်ရိုက်နောက်ဆုံးဒြပ်စင်ပြီးနောက်ပထမ ဦး ဆုံးဒြပ်စင်မှဖြတ်သန်းနိုင်ပါသည်။ ကျွန်ုပ်တို့သည်ဆက်တိုက်ဒြပ်စင်များအကြားကွဲပြားခြားနားချက်အများဆုံးပမာဏကိုရှာဖွေရန်ကျွန်ုပ်တို့အားတောင်းဆိုခဲ့သည်။ ပြီးတော့ကျွန်တော်တို့က array ကိုပြန်စီဖို့အားသာချက်ရှိတယ်။ ကျွန်ုပ်တို့သည်ကွဲပြားခြားနားမှုများ၏ပေါင်းလဒ်ကိုတိုးမြှင့်နိုင်သည်ကိုထိုကဲ့သို့သော။

ဒီမှာကျတော့ array ပေးထားတယ်။ ကျနော်တို့ကတကယ်တော့ခင်းကျင်းပြန်စီစဉ်မသွားကြသည်, ငါတို့ရိုးရှင်းစွာ၎င်း၏နံပါတ်များနှင့်အတူကစားနိုင်ပါတယ်။ အခုကျန်တဲ့ array ရဲ့ထက်ဝက်ကိုပဲဖြတ်သွားရတော့မယ်။ ၎င်းသည် n / 2 အရှည်အထိသာဖြစ်သည်။ n ကခင်းကျင်းခြင်း၏အမှန်တကယ်အရှည်ဖြစ်သည်။ output ကိုခေါ်တဲ့ variable တစ်ခုကိုကြေငြာလိုက်ပြီ။ ဘယ် array ရဲ့ကွဲပြားခြားနားမှုကိုရမယ့်သည်။ ပြီးတော့အဲဒါကိုပေါင်းပြီး output ကိုသိုလှောင်ပါ။ ဒါပေမယ့် array ကိုမဖြတ်ခင်ကျွန်တော်တို့ array ကိုစီရလိမ့်မယ်။ ကျနော်တို့က array ကိုထိုကဲ့သို့သောတိုးမြှင့်နိုင်ရန်အတွက်ဖြစ်သင့်ကြောင်းစီစီသွားကြသည်။ ပြီးနောက် sorting ကျွန်တော်တို့က array ထဲမှာအနိမ့်ဆုံးကိန်းဂဏန်းရှိတဲ့ array က array ရဲ့စဖြစ်တယ်။ ပြီးတော့ array ထဲမှာပိုကြီးတဲ့အရေအတွက်က array ရဲ့အဆုံးမှာဖြစ်တယ်။

ကျွန်ုပ်တို့သည် array ကိုစီစဉ်ထားသဖြင့်ကျွန်ုပ်တို့သည်ခင်းကျင်းသည့်အရှည်၏ထက်ဝက်အထိသာခင်းကျင်းရန်ဖြတ်သန်းသွားရန်လိုအပ်သည်။ ထိုအခါကျွန်ုပ်တို့သည်စစ်ခင်းကျင်းမှု၏တန်ဖိုးနှင့် output တန်ဖိုးတို့၏နှစ်ဆကွာခြားမှုကိုရရှိပြီး၎င်းကို output သို့သိမ်းထားသည်။ ဒီမှာကျွန်တော်တို့ကခြားနားချက်ကိုရတယ်၊ ပြီးရင် array ရဲ့နောက်ဆုံးတန်ဖိုးကိုနှစ်ဆရမယ်။ ပြီးရင် output value ကိုထည့်ပြီး output ထဲမှာသိမ်းထားပါ။ Array ၏အရှည်၏ထက်ဝက်မပြည့်မှီအထိ၎င်းကိုဆက်လက်ထားရှိပြီး output ၏တန်ဖိုးကိုပြန်ပို့ပါ။

ကုဒ်

C ++ code သည် circular array အတွင်းကွဲပြားခြားနားမှုအမျိုးမျိုးကိုပေါင်းနိုင်သည်

#include<iostream>
#include<algorithm>

using namespace std;

int getMaxDiff(int arr[], int n)
{
    int output = 0;

    sort(arr, arr + n);

    for (int i = 0; i < n/2; i++)
    {
        output -= (2 * arr[i]);
        output += (2 * arr[n - i - 1]);
    }

    return output;
}
int main()
{
    int arr[] = { 9, 8, 2, 4 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaxDiff(arr, n) << endl;
    return 0;
}
22

Java code သည် circular array အတွင်းကွဲပြားခြားနားမှုအမျိုးမျိုးကိုပေါင်းစပ်ရန်

import java.util.Arrays;

class maximumDiff
{
    public static int getMaxDiff(int arr[], int n)
    {
        int output = 0;

        Arrays.sort(arr);

        for (int i = 0; i < n/2; i++)
        {
            output -= (2 * arr[i]);
            output += (2 * arr[n - i - 1]);
        }

        return output;
    }
    public static void main (String[] args)
    {
        int arr[] = {9, 8, 2, 4 };
        int n = arr.length;
        System.out.println(getMaxDiff(arr, n));
    }
}
22

ရှုပ်ထွေးဆန်းစစ်ခြင်း

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

အို (n log n) ဘယ်မှာ “ n” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ ဘာလို့လဲဆိုတော့ငါတို့က array ကိုခွဲထားတာလေ။ ဒီတော့အချိန်ရှုပ်ထွေးမှုကပေါင်းစည်းမှုမျိုးလိုဖြစ်လာတယ်။ ကြောင်းအချိန်ရှုပ်ထွေး၏အထက်ခညျြနှောငျခြေတစ်လှမ်းရကတည်းက။

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

အို (၁) အဘယ်သူမျှမပိုအာကာသလိုအပ်သည်အဖြစ်။ ဒီတော့ algorithm ကလိုအပ်တဲ့ space ရှုပ်ထွေးမှုကအမြဲတမ်းရှိနေတယ်။ သို့သော်အစီအစဉ်တစ်ခုလုံး၏ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။