Տրված տիրույթի շուրջ զանգվածի երեք եղանակով բաժանում  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են BankBazaar Blackrock Capital One Միջնաբերդ Ֆաբ Moonfrog լաբորատորիաներ Սինոփսիս Twilio Անտաշ անասուն նողկալի արարած
Դասավորություն

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

Ձեզ տրված է դասավորություն of ամբողջական թվերը և ցածր արժեքի և բարձր արժեքի մի շարք: «Anանգվածի երեք եղանակով բաժանում տվյալ տիրույթի շուրջ» խնդիրը խնդրում է զանգվածը բաժանել այնպես, որ զանգվածը բաժանվի երեք մասի: Raանգվածների բաժանումները կլինեն.

  1. Առաջին բաժանման տարրերը ցածր կլինեն ցածր արժեքից,
  2. Հաջորդ միջնորմը, որի տարրերը գտնվում են տվյալ տիրույթում, կլինի այս բաժանման մեջ և
  3. HighValue- ից մեծ թվերը կլինեն զանգվածի երրորդ բաժին:

Օրինակ  

arr[]={2,5,87,56,12,4,9,23,76,1,45}

lowValue = 15

highValue = 30
2 5 1 12 4 9 23 76 56 45 87

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

lowValue- ը 15 է, այնպես, որ ձախ կողմում թվերը պակաս լինեն ցածր արժեքից:

Միջակայքը 15-ից 30-ի սահմաններում է, 23-ը `այն թիվը, որը ընկած է այս միջակայքի միջև

highValue- ը 30 է, բարձր արժեքից մեծ բոլոր թվերը կլինեն աջ կողմում:

Տրված տիրույթի շուրջ զանգվածի երեք եղանակով բաժանումPin

Ալգորիթմ  

1. Set the startingValue to 0 and endingValue to n-1.
2. Traverse the array.
    1. Check if the current array element is less than the value of lowValue if true then swap the arr[i] and arr[startingValue] and increase both startingValues and i by 1.
    2. Else check if the current array is greater than the highValue, swap the arr[i] and arr[endingValue] and increase the value of i and decrease the value of endingValue by 1.
    3. Else increase the value of i by 1.
3. Print the array.

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

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

Տես նաեւ,
Ենթանկարի առավելագույն չափի գումարը հավասար է k- ի

Մենք կկողմնորոշվենք զանգվածը ՝ 0-իցth ինդեքսը մինչեւ վերջին ցուցանիշը: Բայց մինչ այդ, մենք հայտարարել ենք որոշ փոփոխականների մասին և նախաձևակերպում ենք դրանք, համապատասխանաբար, զանգվածի 0 և վերջին ցուցիչներով: Փոխանակման ժամանակ, երբ ցածր արժեքից ցածր արժեք է հայտնաբերվում, գործողությունը կկատարվի մեկնարկային արժեքի վրա, և երբ հայտնաբերված բարձր արժեքից ավելի մեծ արժեք, այդ դեպքում գործողությունը կկատարվի վերջավոր արժեքի վրա: Մենք կկողմնորոշենք զանգվածը և ստուգենք ՝ արդյո՞ք զանգվածի ընթացիկ տարրը պակաս է տրված ցածր արժեքից, եթե ճիշտ է, ապա փոխանակենք զանգվածի ընթացիկ արժեքը և զանգվածի առաջին դիրքի արժեքը: Այս արժեքը մենք հետևելու ենք ելակետին, իսկ մյուս արժեքը հետևելու է տարրերի փոխանակման վերջի ինդեքսներին, և մեկ այլ փոխանակում կկատարվի, եթե տարրը գտնվի ընթացիկ զանգվածի արժեքից մեծ: Դրանից հետո գալիս է վերջավորության արժեքը, ինդեքսը, որի դեպքում տարրը փոխվում է ընթացիկ տարրի հետ: Եթե ​​պայմաններից ոչ մեկը չի բավարարում, նշանակում է, որ տվյալ թիվը գտնվում է տվյալ տիրույթում, ապա մենք այն չենք փոխում: Անցումն ավարտելուց հետո մենք ունենք ցանկալի զանգված: Մենք պարզապես պետք է տպենք զանգվածը:

Կոդ  

C ++ կոդ ՝ տվյալ տիրույթի շուրջ զանգվածի եռակողմ բաժանումը լուծելու համար

#include<iostream>
using namespace std;

void getPartition(int arr[], int n, int lowValue, int highValue)
{
    int startingValue = 0, endingValue = n-1;

    for (int i=0; i<= endingValue;)
    {
        if (arr[i] < lowValue)
            swap(arr[i++], arr[startingValue++]);

        else if (arr[i] > highValue)
            swap(arr[i], arr[endingValue--]);

        else
            i++;
    }
}

int main()
{
    int arr[] = {2,5,87,56,12,4,9,23,76,1,45};
    int n = sizeof(arr)/sizeof(arr[0]);

    getPartition(arr, n, 15, 30);

    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
2 5 1 12 4 9 23 76 56 45 87

Տվյալ տիրույթի շուրջ զանգվածի եռակողմ բաժանումը լուծելու համար Java կոդ

class ThreeWayPartition
{
    public static void getPartition(int[] arr, int lowValue, int highValue)
    {
        int n = arr.length;

        int startingValue = 0, endingValue = n-1;

        for(int i = 0; i <= endingValue;)
        {
            if(arr[i] < lowValue)
            {

                int temp = arr[startingValue];
                arr[startingValue] = arr[i];
                arr[i] = temp;
                startingValue++;
                i++;
            }
            else if(arr[i] > highValue)
            {

                int temp = arr[endingValue];
                arr[endingValue] = arr[i];
                arr[i] = temp;
                endingValue --;
            }
            else
                i++;
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {2,5,87,56,12,4,9,23,76,1,45};

        getPartition(arr, 15, 30 );

        for (int i=0; i < arr.length; i++)
        {
            System.out.print(arr[i] + " ");

        }
    }
}
2 5 1 12 4 9 23 76 56 45 87

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

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

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք թերթել ենք զանգվածի տարրերը, ժամանակի բարդությունը գծային է:

Տես նաեւ,
Խառնել Array Leetcode լուծումը

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

Ո (1) քանի որ լրացուցիչ տարածք չի պահանջվում: Ալգորիթմն ինքնին իր տեղում է և թարմացնում է տրված նախնական զանգվածը: Այսպիսով, ալգորիթմի տիեզերական բարդությունը կայուն է, մինչդեռ ծրագիրը գծային է: