Массивди берилген аралыктагы үч тараптуу бөлүү  


Кыйынчылык деңгээли жеңил
Көп суралган BankBazaar Кара таш Capital One Citadel Fab Moonfrog Labs Synopsys Twilio Yahoo
согуштук тизме

Маселени билдирүү  

Сизге ан согуштук тизме of бүтүн жана lowValue жана highValue катарлары. Массивди "берилген аралыктагы үч тараптуу бөлүү" маселеси массивди үч бөлүккө бөлүп тургандай кылып бөлүүнү суранат. Массивдин бөлүктөрү:

  1. Биринчи бөлүктүн элементтери төмөнValueден азыраак болот,
  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 дан чоңураак сандар оң жагында болот.

Массивди берилген аралыктагы үч тараптуу бөлүүтөөнөч

Algorithm  

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 дан төмөн болгон бардык мүмкүн болгон сандары массивдин сол жагында болот. Ал эми массивдин диапазонунун ортосунда турган массивдин саны массивде кийинки болот. Ал эми кийинки баалуулуктар, жогору болгон маанидегиден чоңураак болгон сандар акыркы болуп калат.

ошондой эле
Максималдуу өлчөм subarray суммасы k барабар

Биз 0дон баштап, массивди аралап өтөбүзth акыркы индекске индекс. Бирок ага чейин биз кандайдыр бир өзгөрүлмө деп жарыялаганбыз жана аны 0 жана массивдин акыркы индекси менен баштайбыз. Алмашуу учурунда, lowValue дан төмөн маани табылганда, аракет баштапкыValueде аткарылат жана табылган highValueден чоң болгондо, операция endValueде аткарылат. Биз массивди айланып өтүп, учурдагы массивдин элементи берилген 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" массивдеги элементтердин саны. Массив элементтерин аралап өткөндүктөн, убакыттын татаалдыгы сызыктуу.

ошондой эле
Массив Leetcode чечимин аралаштырыңыз

Космостун татаалдыгы

O (1) ашыкча орун талап кылынбагандыктан. Алгоритм өзү алгоритм болуп саналат жана баштапкы массивди жаңыртып жатат. Ошентип, алгоритмдин мейкиндик татаалдыгы туруктуу, ал эми программа сызыктуу.