ثلاث طرق لتقسيم المصفوفة حول نطاق معين


مستوى الصعوبة سهل
كثيرا ما يطلب في بنك بازار بلاك روك عاصمة واحدة قلعة القوات المسلحة البوروندية مختبرات Moonfrog سينوبسيس Twilio ياهو
مجموعة

المشكلة بيان

يتم منحك ملف مجموعة of الأعداد الصحيحة ومجموعة من lowValue و highValue. تتطلب مشكلة "تقسيم المصفوفة ثلاثية الاتجاهات حول نطاق معين" تقسيم المصفوفة بحيث يتم تقسيم المصفوفة إلى ثلاثة أجزاء. ستكون أقسام المصفوفات:

  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 على الجانب الأيسر من المصفوفة. وسيكون رقم المصفوفة الذي يقع بين نطاق المصفوفة هو التالي في المصفوفة. وستكون القيم التالية هي الأرقام التي تكون أكبر من القيمة العالية ستكون الأخيرة.

سنقوم باجتياز المصفوفة من الصفرth الفهرس إلى الفهرس الأخير. ولكن قبل ذلك ، أعلنا عن بعض المتغيرات وقمنا بتهيئتها باستخدام 0 والفهرس الأخير للصفيف على التوالي. عند التبديل كلما تم العثور على قيمة أقل من lowValue ، سيتم تنفيذ العملية على قيمة البداية وكلما كانت القيمة أكبر من قيمة 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) حيث لا توجد مساحة إضافية مطلوبة. الخوارزمية نفسها هي خوارزمية موضعية وتقوم بتحديث المصفوفة الأولية المحددة. وبالتالي فإن تعقيد مساحة الخوارزمية ثابت بينما يكون البرنامج خطيًا.