Փոխարինեք երկու հաջորդական հավասար արժեքներ մեկով ավելի մեծով


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Accenture Միջնաբերդ Անվճար լիցքավորում PayPal քառակուսի Տերադատա
Դասավորություն

Խնդիրի հայտարարություն

Ենթադրենք, որ դուք ունեք ամբողջ թիվ դասավորություն, «Երկու անընդմեջ հավասար արժեքները փոխարինիր մեկ մեծով» խնդիրը պահանջում է փոխարինել «ա» բոլոր այդ զույգ արժեքները, որոնք հաջորդաբար գալիս են իրենցից մեծ «ա +1» թվով (երկու հաջորդական թվերով), այնպես, որ նույնիսկ փոփոխությունից հետո կամ կրկնություն չի մնա նոր հաջորդական զույգ:

Օրինակ

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

բացատրություն

Քանի որ 1-ը անընդմեջ թիվ է, այն փոխարինվում է ավելի մեծ արժեքով, քան նշանակում է 2, իսկ arr- ը կդառնա {5,2,2,2,2}

Այժմ 2-ը հաջորդական թիվ է, ուստի այն կփոխարինվի դրանից մեծ թվով, այսինքն, 3-ը և ar- ը կդառնան {5,3,2,2}

Կրկին 2-ը անընդմեջ թիվ է, ուստի այն կփոխարինվի 3-ով, իսկ arr- ը կդառնա {5,3,3}

Այժմ 3-ը հաջորդական թիվ է, ուստի այն կփոխարինվի 4-ով, իսկ տողը կդառնա {5,4}

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

բացատրություն

Քանի որ 5-ը անընդմեջ թիվ է, այն փոխարինվում է 1-ից մեծ արժեքով, քան 6-ը: Այսպիսով, arr- ը կարծես arr լինի [] = {2,6,6,2,7,7}

6-ը գալիս է դրա փոխարեն, բայց հաջորդ թիվը նույնպես 6-ն է, ուստի այն նաև փոխարինվում է 1-ից 6-ով մեծ արժեքով, նշանակում է, որ 7-ը և arr- ը կդառնան {2,7,2,7,7}

Քանի որ 7-ը նույնպես վերջապես տեղի է ունենում անընդմեջ, ուստի այն փոխարինվում է 8-ով և arr- ը կդառնա {2,7,2,8}

Ալգորիթմ

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-ով ավելի մեծ թվով, քան ինքը: Եթե ​​4-ը անընդմեջ զանգվածներ գա, ապա այն կփոխարինվի 5 արժեքով: Դա 1-ով մեծ է թիվ 4-ից: Այժմ մեկ անցումով, մենք կարող ենք միայն փոփոխություն կատարել: Ենթադրենք, կա 3, 4, 4 ներկա 5 թվեր: Այնուհետև մենք 4, 4-ը կվերածենք 5-ի, ապա նաև 5-ը հաջորդական թիվ է: Քանի որ նրա հաջորդ համարը նույնն է, ինչ ինքը: Այսպիսով, մենք դա կանենք ՝ օգտագործելով տեղադրված օղակ:

Անցեք զանգվածը 0-ից n: Բացեք մի օղակ, այնպես որ այն կդառնա տեղադրված օղակ: Արտաքին օղակով մենք կվարվենք անցումներին: Եվ ներքին օղակով մենք պատրաստվում ենք թարմացնել արժեքները կամ փոխարինել արժեքները ՝ ըստ տվյալ պայմանի: Արտաքին օղակում մենք պատրաստվում ենք պատճենել նույն զանգվածի արժեքները մինչև երկու արժեք:

Միայն արտաքին օղակի երկու անցումից հետո այն կընթանա ներքին օղակի մեջ: Մեջ իսկ հանգույց, մենք պատրաստվում ենք ստուգել, ​​արդյոք ցուցանիշների արժեքը 1-ից մեծ է, քանի որ մենք համեմատելու ենք, եթե նախորդ երկու արժեքները հավասար են: Այդ պատճառով մենք թողնում ենք այդ պայմանը, որ երկու արժեք պետք է պատճենվի զանգվածի վրա տեղակայված արժեքների մեջ: Ապա պարզապես իջեցրեք դիրքի արժեքները և թարմացրեք զանգվածի տարրը 1 թվից մեծ արժեքներով: Մենք պարզապես կշարունակենք այս օղակը և այս մեթոդը: Այն շարունակաբար այդ բոլոր արժեքները փոխարինելու է հաջորդականներով:

Այժմ տպեք զանգվածը 0-ից ինդեքսի դիրքի վրա, որը վերջին անգամ թարմացվել է, այն կտա ցանկալի զանգված:

Փոխարինեք երկու հաջորդական հավասար արժեքներ մեկով ավելի մեծով

 

Կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

Վրա2որտեղ«Ն» զանգվածում տարրերի քանակն է. Քանի որ մենք օգտագործել ենք երկու տեղադրված օղակ, որոնք ստիպել են ալգորիթմը գործել բազմանդամ ժամանակում:

Տիեզերական բարդություն

O (1), դա անկախ է զանգվածի տարրերի քանակից. Ալգորիթմն ինքնին անընդհատ տարածություն է զբաղեցնում, բայց ծրագիրն, ընդհանուր առմամբ, տանում է O (N) տարածք (մուտքագրման համար):