Тристороннє розділення масиву навколо заданого діапазону  


Рівень складності Легко
Часто запитують у БанкБазаар BlackRock Capital One Цитадель Fab Лабораторії Moonfrog Синопсис Twilio Yahoo
масив

Постановка проблеми  

Вам дано масив of цілих чисел і діапазон низького і високого значення. Проблема "Тристороннє розділення масиву навколо заданого діапазону" просить розділити масив таким чином, що масив буде розділений на три частини. Розділами масивів будуть:

  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, так що цифри в лівій частині будуть менше ніж lowValue.

Діапазон між 15 і 30, 23 - це число, яке лежить між цим діапазоном

highValue - 30, усі цифри, більші за highValue, будуть з правого боку.

Тристороннє розділення масиву навколо заданого діапазону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.

Пояснення  

Ми дали цілочисельний масив та діапазон lowValue та highValue. Ми маємо впорядкувати масив або розділити масив. Такі, що всі можливі номери масиву, які є меншими за низьке значення, будуть у лівій частині масиву. І номер масиву, який лежить між діапазоном масиву, буде наступним у масиві. І наступними значеннями будуть цифри, які більші, ніж високе значення, буде останнім.

Дивись також
Сума підмасиву максимального розміру дорівнює k

Ми будемо обходити масив, починаючи з 0th індекс до останнього індексу. Але до цього ми оголосили деяку змінну та ініціалізуємо її відповідно 0 та останнім індексом масиву. При обміні, коли буде знайдено значення, нижче ніж низьке значення, операція буде виконуватися над початковим значенням, і коли значення, що перевищує значення високого значення, операція виконується в кінці значення. Ми здійснимо обхід масиву та перевіримо, чи поточний елемент масиву менше заданого lowValue, якщо true, поміняємо місцями поточне значення масиву та значення першої позиції масиву. За цим значенням ми будемо відстежувати початкову точку, а за іншим значенням - відстежувати кінцеві індекси для обміну елементами, інший обмін буде здійснено, якщо елемент виявиться більшим за значення поточного елемента масиву. Потім настає ENDVALUE, індекс, при якому елемент замінюється поточним елементом. Якщо жодна умова не задовольняє, означає, що число лежить у заданому діапазоні, ми не змінюємо його. Після завершення обходу ми маємо бажаний масив. Нам просто потрібно надрукувати масив.

код  

Код С ++ для вирішення Тристороннє розділення масиву навколо заданого діапазону

#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

Аналіз складності  

Складність часу

О (п) де "N" - кількість елементів у масиві. Оскільки ми здійснили обхід елементів масиву, складність часу є лінійною.

Дивись також
Перетасувати рішення масиву Leetcode

Складність простору

O (1) оскільки додатковий простір не потрібен. Сам алгоритм є місцевим алгоритмом і оновлює початковий заданий масив. Таким чином, космічна складність алгоритму є постійною, тоді як програма є лінійною.