Трипосочно разделяне на масив около даден диапазон


Ниво на трудност Лесно
Често задавани в BankBazaar BlackRock Capital One Цитадела Fab Moonfrog Labs Synopsys Twilio Yahoo
Array

Декларация за проблема

Вие получавате масив of числа и диапазон от ниска и висока стойност. Проблемът „Трипосочно разделяне на масив около даден диапазон“ иска да се раздели масива така, че масивът да бъде разделен на три части. Разделите на масивите ще бъдат:

  1. Елементите на първия дял ще бъдат по-малки от lowValue,
  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, така че числата в лявата страна ще бъдат по-малки от lowValue.

Диапазонът е между 15 и 30, 23 е числото, което се намира между този диапазон

highValue е 30, всички числа, по-големи от highValue, ще бъдат от дясната страна.

Трипосочно разделяне на масив около даден диапазон

алгоритъм

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, ще бъдат в лявата страна на масива. И номерът на масива, който се намира между обхвата на масива, ще бъде следващият в масива. И следващите стойности ще бъдат числата, които са по-големи от highValue, ще бъдат последните.

Ще прекосим масива от 0th индекс до последния индекс. Но преди това сме декларирали някаква променлива и я инициализираме съответно с 0 и последния индекс на масива. При размяна, когато се намери стойност, по-ниска от lowValue, операцията ще се извърши на startValue и когато стойността е по-голяма от highValue, тогава операцията ще се извърши в endValue. Ще преминем през масива и ще проверим дали текущият елемент на масива е по-малък от даденото lowValue, ако е вярно, след това разменете текущата стойност на масива и стойността на първата позиция на масива. Тази стойност ще проследяваме началната точка, а другата стойност ще следи крайните индекси за размяна на елементи, ще се извърши друга размяна, ако елементът бъде намерен по-голям от стойността на текущия елемент на масива. След това идва ENDVALUE, индекс, при който елементът се разменя с текущия елемент. Ако никое от условията не удовлетворява, означава, че числото се намира в дадения диапазон, тогава не го променяме. След завършване на обхода имаме желания масив. Просто трябва да отпечатаме масива.

код

Код на 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 (1) тъй като не се изисква допълнително пространство. Самият алгоритъм е алгоритъм на място и актуализира първоначално дадения масив. По този начин пространствената сложност на алгоритъма е постоянна, докато програмата е линейна.