Массивті берілген ауқым бойынша үш жақты бөлу


Күрделілік дәрежесі оңай
Жиі кіреді BankBazaar BlackRock Capital One Цитадель Фаб Moonfrog зертханалары Synopsys Twilio Yahoo
Array

Проблемалық мәлімдеме

Сізге ан массив of бүтін сандар және lowValue және highValue диапазоны. «Массивті берілген ауқым бойынша үш жақты бөлу» мәселесі массивті үш бөлікке бөлетін етіп массивті бөлуді сұрайды. Массивтің бөлімдері:

  1. Бірінші бөлімнің элементтері төмен мәннен аз болады,
  2. Элементтер берілген аралықта орналасатын келесі бөлім осы бөлімде және болады
  3. Жоғары мәннен үлкен сандар жиымның үшінші бөлімі болады.

мысал

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, сол жақтағы сандар lowValue мәнінен аз болатындай етіп XNUMX құрайды.

Ауқым 15 пен 30 аралығында, 23 - бұл осы аралықта орналасқан сан

highValue 30, ал жоғары мәннен үлкен сандар оң жақта орналасады.

Массивті берілген ауқым бойынша үш жақты бөлу

Алгоритм

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.

Түсіндіру

Біз бүтін массивті және lowValue және highValue диапазонын бердік. Біз массивті немесе бөлімді бөлуге тиіспіз. Массивтің lowValue мәнінен кіші барлық мүмкін сандары жиымның сол жағында болатындай. Ал жиымның ауқымы арасында орналасқан жиымның саны жиымның келесі бөлігінде болады. Келесі мәндер жоғары мәннен үлкен сандар болады, олар соңғы болады.

Біз 0-ден бастап массивті айналып өтемізth соңғы индекске индекс. Бірақ бұған дейін біз кейбір айнымалыларды жариялап, оны сәйкесінше 0 және массивтің соңғы индексімен инициализациялаймыз. Ауыстыру кезінде lowValue мәнінен төмен мән табылған кезде, амал бастапқы мәнде орындалады, ал табылған highValue мәнінен үлкен болған сайын операция соңы мәнде орындалады. Біз массивті айналып өтіп, массивтің ағымдағы элементі берілген lowValue мәнінен аз екенін тексереміз, егер true болса, массивтің ағымдағы мәнін және массивтің бірінші позиция мәнін ауыстырамыз. Бұл мән біз бастапқы нүктені және басқа мән элементтерді ауыстыру үшін аяқталатын индекстерді қадағалайды, егер элемент ағымдағы массив элементінің мәнінен үлкен болса, тағы бір своп жасалады. Содан кейін элемент ағымдағы элементпен ауыстырылатын endingValue индексі шығады. Егер шарттардың ешқайсысы қанағаттандырылмаса, сан берілген диапазонда орналасқан болса, біз оны өзгертпейміз. Өту аяқталғаннан кейін бізде қажетті массив болады. Біз тек массивті басып шығаруымыз керек.

код

Шешуге арналған 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

Күрделілікті талдау

Уақыттың күрделілігі

O (N) қайда «N» - массивтегі элементтер саны. Біз массив элементтерін аралап өткендіктен, уақыт күрделілігі сызықтық болып табылады.

Ғарыштың күрделілігі

O (1) өйткені қосымша орын қажет емес. Алгоритм өзі алгоритм болып табылады және бастапқы берілген жиымды жаңартады. Сонымен, алгоритмнің кеңістік күрделілігі тұрақты, ал бағдарлама сызықтық болып табылады.