Bir sıra verilən bir sıra ətrafında üç yollu bölüşdürmə

Çətinlik səviyyəsi Asan
Tez-tez soruşulur BankBazaar BlackRock Capital One Citadel Fab Moonfrog Laboratoriyaları Sinopsis Twilio Yahoo
GeyimBaxılıb 27

Problem bəyanat

Sizə verilir array of tamsayılar və bir sıra lowValue və highValue. Məsələ “Verilən aralıq ətrafında bir massivin üçlü bölüşdürülməsi” məsələsi, massivin üç hissəyə bölünəcəyi şəkildə bölünməsini xahiş edir. Dizilərin bölmələri:

  1. Birinci bölümün elementləri aşağı Dəyərdən daha az olacaq,
  2. Elementlərin verilən aralığa yerləşməsi üçün növbəti bölmə bu bölmədə və
  3. HighValue-dən böyük rəqəmlər massivin üçüncü bölməsi olacaqdır.

misal

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

Izahat

lowValue 15-dir, belə ki sol tərəfdəki ədədlər lowValue-dan az olacaq.

Aralıq 15 ilə 30 arasındadır, 23 bu aralıq arasında olan rəqəmdir

highValue 30, highValue-dən böyük olan bütün nömrələr sağ tərəfdə olacaq.

Bir sıra verilən bir sıra ətrafında üç yollu bölüşdürməPin

Alqoritm

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.

Izahat

Tam bir sıra və lowValue və highValue aralığını verdik. Dizini düzəltməliyik və ya serialı bölməliyik. Dizinin lowValue-dan az olan bütün mümkün nömrələri massivin sol tərəfində olacaq. Və sıra aralığı arasında olan massivin sayı massivdə növbəti olacaqdır. Növbəti dəyərlər, yüksəkDəyərin sonuncusundan böyük olan ədədlər olacaqdır.

0-dan başlayaraq serialı gəzəcəyikth son göstəriciyə indeks. Ancaq bundan əvvəl bəzi dəyişənlər elan etdik və sırasıyla 0 və serialın son indeksi ilə başladık. Dəyişiklikdə, lowValue-dən aşağı qiymət tapıldıqda əməliyyat startValue-də və tapılan highValue-dən daha yüksək olan zaman yerinə yetiriləcək, sonra endingValue-da əməliyyat aparılacaqdır. Dizini keçəcəyik və cari massiv elementinin verilmiş lowValue-dan az olub olmadığını yoxlayacağıq, əgər doğrudursa, massivin cari dəyərini və massivin birinci mövqe dəyərini dəyişdiririk. Bu dəyər başlanğıc nöqtəsini izləyəcəyik və digər dəyər elementləri dəyişdirmək üçün bitən indeksləri izləyəcək, element cari array elementinin dəyərindən daha çox tapılarsa başqa bir mübadilə ediləcəkdir. Sonra elementin cari elementlə dəyişdirildiyi endingValue indeksi gəlir. Əgər şərtlərdən heç biri yerinə yetirmirsə, rəqəm verilən aralığın içindədir demək deyilsə, onu dəyişdirmirik. Keçid tamamlandıqdan sonra istədiyimiz sıra var. Yalnız serialı çap etməliyik.

Kodu

C ++ kodunu həll etmək üçün bir sıra verilmiş bir aralığın üçlü bölüşdürülməsi

#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

Bir kodun müəyyən bir aralığın üçlü bölüşdürülməsini həll etmək üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara "N" massivdəki elementlərin sayıdır. Massiv elementlərinin üstündən keçdiyimiz üçün zamanın mürəkkəbliyi xətti olur.

Kosmik Mürəkkəblik

O (1) əlavə yer tələb olunmadığı üçün. Alqoritm özü yerində olan alqoritmdir və verilmiş ilkin massivi yeniləyir. Beləliklə, proqram xətti olduğu halda alqoritmin kosmik mürəkkəbliyi sabitdir.

Translate »