နှစ်ခုဆက်တိုက်တန်းတူတန်ဖိုးများကိုသာ။ ကြီးမြတ်သောတစ်ခုနှင့်အစားထိုးပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Accenture Citadel FreeCharge PayPal က ရင်ပြင် Teradata
အခင်းအကျင်း

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

မင်းမှာကိန်းပြည့်ရှိတယ်ဆိုပါစို့ အခင်းအကျင်း။ “ ဆက်တိုက်တန်းတူတန်ဖိုးနှစ်ခုကိုတစ်ခုနှင့်တစ်ခုအစားထိုးပါ” ပြproblemနာက pair တစုံရဲ့တန်ဖိုးတွေအားလုံးကိုအစားထိုးဖို့တောင်းဆိုတဲ့ 'a' ၁ ထက်ပိုကြီးတဲ့ "a + 1" နံပါတ် (နှစ်ဆက်တိုက်နံပါတ်နှစ်ခု) နဲ့အစားထိုးဖို့ပြောတယ်။ သို့မဟုတ်ထပ်ခါတလဲလဲအသစ်သောဆက်တိုက် pair တစုံကျန်ကြွင်းလိမ့်မည်။

နမူနာ

arr[]={5, 2, 1, 1, 2, 2}
5 4

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

1 သည်ဆက်တိုက်နံပါတ်ဖြစ်သဖြင့်၎င်းကို 2 ထက်ကြီးသောတန်ဖိုးဖြင့်အစားထိုးသည်။ arr သည် {5,2,2,2,2} ဖြစ်လာလိမ့်မည်။

ယခု 2 သည်ဆက်တိုက်ကိန်းဖြစ်သဖြင့်၎င်းထက်ကြီးသောကိန်းဖြင့်အစားထိုးမည်။ ဆိုလိုသည်မှာ 3 နှင့် arr သည် {5,3,2,2} ဖြစ်လာလိမ့်မည်။

ထပ်မံ၍ 2 သည်ဆက်တိုက်ကိန်းဖြစ်သဖြင့် 3 အစားထိုးပါလိမ့်မည်။ arr သည် {5,3,3} ဖြစ်လာလိမ့်မည်။

ယခု 3 သည်ဆက်တိုက်ကိန်းဖြစ်သဖြင့် ၄ အစားထိုးပါလိမ့်မည်။ arr သည် {4} ဖြစ်လာလိမ့်မည်။

arr[]={2,5,5,6,2,7,7}
2 7 2 8

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

5 သည်အဆက်မပြတ်သောနံပါတ်တစ်ခုဖြစ်ခြင်းကြောင့်၎င်းသည် ၆ ထက် ပို၍ ကြီးသောတန်ဖိုး ၁ ဖြင့်အစားထိုးသည်။ ထို့ကြောင့် arr သည် arr [] = {1} နှင့်တူလိမ့်မည်။

6 သည်ထိုနေရာမှလာသည်။ နောက်နံပါတ်သည်လည်း ၆ ဖြစ်သည်။ ထို့ကြောင့်၎င်းကို ၆ ထက်ကြီးသောတန်ဖိုးနှင့်အစားထိုးသည်။ ၇ ကိုဆိုလိုသည်။ arr သည် {6} ဖြစ်လာလိမ့်မည်။

7 သည်နောက်ဆုံးတွင်အဆက်မပြတ်ဖြစ်ပေါ်နေသောကြောင့်၎င်းကို 8 နှင့်အစားထိုးခြင်းနှင့် arr သည် {2,7,2,8} ဖြစ်လာလိမ့်မည်။

algorithm

1. Set the position’s value to 0.
2. Traverse the array from o to n(n is the length of the array).
  1. Copy the value of arr[i] to arr[position] and increase the value of the position by 1.
  2. While the position is greater than 1, its previous two values are equal or not.
    1. Decrease the value of a position by 1,
    2. and increase the value of arr[position -1] by 1.
3. Print the array from index 0 to position.

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

ငါတို့ပေးထားတယ် အခင်းအကျင်း of ကိန်း။ ကျွန်ုပ်တို့သည်နံပါတ်များထက်သာလွန်သောနံပါတ် ၁ နှင့်ဆက်တိုက်ပါ ၀ င်သောတန်ဖိုးအားလုံးကိုအစားထိုးရန်ကျွန်ုပ်တို့တောင်းဆိုခဲ့သည်။ အကယ်၍ 1 သည် Array များဆက်တိုက်ရောက်လာလျှင်၊ ၎င်းကိုတန်ဖိုး ၅ နှင့်အစားထိုးလိမ့်မည်။ ၄ သည်နံပါတ် ၄ ထက် ပို၍ ကြီးသည်။ ယခု traversal တစ်ခုဖြင့်သာပြုပြင်နိုင်သည်။ ဆိုပါစို့၊ ဂဏန်း ၃ ခုရှိတယ် ၄၊ ၄၊ ၅ ။ ပြီးတော့ငါတို့က ၄၊ ၄ ကနေ ၅ ကိုပြောင်းမယ်၊ ပြီးတော့ ၅ ကထပ်ကိန်းကိန်းဖြစ်လိမ့်မယ်။ ဘာလို့လဲဆိုတော့သူ့ရဲ့နောက်ကိန်းကကိန်းဂဏန်းကိုယ်နှိုက်နဲ့တူလို့ပဲ။ ဒါကြောင့် nested loop ကိုသုံးပြီးငါတို့လုပ်မယ်။

0 မှ n သို့ခင်းကျင်းမှုကိုဖြတ်သန်းပါ။ ကွင်းဆက်တစ်ခုကိုဖွင့်ပါ၊ အပြင်ကလူနှင့်အတူကျွန်ုပ်တို့သည်ဖြတ်သန်းသွားလာခြင်းကိုကိုင်တွယ်လိမ့်မည်။ ထိုအခါအတွင်းပိုင်းကွင်းဆက်နှင့်အတူကျနော်တို့တန်ဖိုးများကို update သို့မဟုတ်ပေးထားသောအခြေအနေနှင့်အညီတန်ဖိုးများကိုအစားထိုးသွားနေကြသည်။ ပြင်ပကွင်းဆက်တွင်၊ တန်ဖိုးများကိုအတူတူပင်ခင်းကျင်းထဲမှတန်ဖိုးများကိုကူးယူသွားမည်။

ပြင်ပကွင်းတွင်ဖြတ်သန်းသွားသောနောက်မှသာ၎င်းသည်အတွင်းပိုင်းကွင်းသို့သွားလိမ့်မည်။ တစ် ဦး အတွက် နေစဉ်ကွင်းဆက်, ငါတို့က indices တနျဖိုးက 1 ထက်ကြီးလားမရကိုစစျဆေးရမယျ။ ဘာလို့လဲဆိုတော့အရင်တန်ဖိုးနှစ်ခုကတူရင်ငါတို့နှိုင်းယှဉ်မယ်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်ထိုအခြေအနေကိုထားခဲ့ပြီးတန်ဖိုးနှစ်ခုကို array positioned values ​​သို့ကူးယူရမည်။ ထို့နောက်ရိုးရိုး position ၏တန်ဖိုးကိုလျှော့ချပြီး array element ကိုနံပါတ်များထက် ပို၍ သာသောအားဖြင့် update လုပ်ပါ။ ဒီကွင်းဆက်နဲ့ဒီနည်းလမ်းကိုပဲဆက်လုပ်သွားမှာပါ။ ၎င်းတန်ဖိုးများအားလုံးကိုဆက်တိုက်တန်ဖိုးများဖြင့်စဉ်ဆက်မပြတ်အစားထိုးလိမ့်မည်။

နောက်ဆုံးပေါ်နောက်ဆုံးပေါ်နောက်ဆုံးဖြစ်သော 0 မှ index အနေအထားကို print ထုတ်ပါ။ ၎င်းသည်လိုချင်သော array ကိုပေးလိမ့်မည်။

နှစ်ခုဆက်တိုက်တန်းတူတန်ဖိုးများကိုသာ။ ကြီးမြတ်သောတစ်ခုနှင့်အစားထိုးပါ

 

ကုဒ်

C ++ ကုဒ်နံပါတ် ၂ ခုဆက်တိုက်တန်းတူတန်ဖိုးများကိုတစ်ခုနှင့်တစ်ခုအစားထိုးရန်

#include<iostream>

using namespace std;

void replaceValues(int arr[], int n)
{
    int position = 0;

    for (int i = 0; i < n; i++)
    {
        arr[position++] = arr[i];
        while (position > 1 && arr[position - 2] == arr[position - 1])
        {
            position--;
            arr[position - 1]++;
        }
    }
    for (int i = 0; i < position; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 2,5,5,6,2,7,7};
    int n = sizeof(arr) / sizeof(int);
    replaceValues(arr, n);
    return 0;
}
2 7 2 8

Java ကုဒ်နှစ်ခုကိုဆက်တိုက်တန်းတူတန်ဖိုးများကိုတစ်ခုထက်ကြီးသောတစ်ခုနှင့်အစားထိုးရန်

class replaceConsecutiveValues
{
    public static void replaceValues(int arr[], int n)
    {
        int position = 0;
        for (int i = 0; i < n; i++)
        {
            arr[position++] = arr[i];
            while (position > 1 && arr[position - 2] == arr[position - 1])
            {
                position--;
                arr[position - 1]++;
            }
        }
        for (int i = 0; i < position; i++)
            System.out.print( arr[i] + " ");
    }
    public static void main(String args[])
    {
        int arr[] = {2,5,5,6,2,7,7};
        int n = arr.length;
        replaceValues (arr, n);
    }
}
2 7 2 8

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

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

အို (။2ဘယ်မှာ“ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်. ဘာကြောင့်လဲဆိုတော့ကျွန်တော်တို့ဟာ polynomial time မှာ run ဖို့ algorithm ကိုလုပ်ထားတဲ့အသိုက်နှစ်ခုကိုအသုံးပြုထားလို့ပဲ။

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

အို (၁)၊ ကြောင်းခင်းကျင်းအတွက်ဒြပ်စင်များ၏အရေအတွက်ကိုလွတ်လပ်သောဖြစ်ပါတယ်. အဆိုပါ algorithm ကိုသူ့ဟာသူစဉ်ဆက်မပြတ်အာကာသကိုကြာပေမယ့်တစ်ဖွဲ့လုံးကအစီအစဉ်ကို (input ကိုများအတွက်) O (N) အာကာသကိုယူ။