מחיצה תלת כיוונית של מערך סביב טווח נתון  


רמת קושי קַל
נשאל לעתים קרובות בנק בזאר בלקרוק קפיטל אחד מצודה פאב מעבדות מונפרוג סינופסיס 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 יהיו בצד שמאל של המערך. ומספר המערך שנמצא בין טווח המערך יהיה הבא במערך. והערכים הבאים יהיו המספרים הגדולים מהערך הגבוה יהיה האחרון.

ראה גם
גודל מערך משנה מקסימלי שווה ל- k

נעבור את המערך, מה- 0th אינדקס לאינדקס האחרון. אבל לפני כן, הכרזנו על משתנה כלשהו ואותחלנו אותו עם האינדקס האחרון והמערך האחרון בהתאמה. בהחלפה בכל פעם שנמצא הערך הנמוך מה- LowValue, הפעולה תבוצע ב- ValueValue ובכל פעם שהערך גדול מה- HighValue שנמצא, אז הפעולה תבוצע בסוף endingValue. נעבור את המערך ונבדוק אם אלמנט המערך הנוכחי נמוך מהערך הנמוך שניתן אם נכון, נחליף את הערך הנוכחי של המערך ואת ערך המיקום הראשון של המערך. ערך זה אנו נעקוב אחר נקודת ההתחלה וערך אחר ישמור על המסלול של אינדקסי סיום להחלפת האלמנטים, החלפה נוספת תעשה אם האלמנט נמצא גדול מערכו של אלמנט המערך הנוכחי. ואז מגיע 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" הוא מספר האלמנטים במערך. מכיוון שעברנו על מרכיבי המערך מורכבות הזמן היא ליניארית.

ראה גם
ערבב את פתרון ה- Array Leetcode

מורכבות בחלל

O (1) מכיוון שלא נדרש מקום נוסף. האלגוריתם עצמו הוא אלגוריתם במקום ומעדכן את המערך הנתון הראשוני. לפיכך מורכבות החלל של האלגוריתם קבועה ואילו התוכנית היא לינארית.