פיצול מערך לתוצאות עוקבות


רמת קושי בינוני
נשאל לעתים קרובות Google
חמדן ערימה

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

דוגמאות

קלט:
arr [] = {1,2,3,3,4,5}
פלט:
נכון
הסבר:
ניתן לפצל את המערך לשתי עוקבות כמו,
תת 1 [] = {1, 2, 3}
תת 2 [] = {3, 4, 5}

קלט:
arr [] = {Z1, 2, 3, 3, 4, 4, 5, 5}
פלט:
נכון
הסבר:
ההמשך העוקב הוא:
תת 1 [] = {1, 2, 3, 4, 5}
תת 2 [] = {3, 4, 5}

פיצול מערך לתוצאות עוקבות

גישה נאיבית למערך מפוצל לתוצאות עוקבות

עבור אלמנט arr [i] של המערך הנתון, הוא יכול ליצור רצף חדש או להוסיף אותו לרצף שמסתיים ב- (arr [i] - 1).

זה תמיד טוב יותר לֹא ליצור המשך חדש כמו היווצרות המשך חדש עלול לגרום לרצפים מסוימים באורך של פחות משלוש. אם אין המשך שמסתיים ב- (arr [i] - 1), אין אפשרות אלא ליצור המשך חדש.

אם יש יותר מסקציות אחד שיכולות להכיל את האלמנט הנוכחי, הוסף תמיד את האלמנט הנוכחי לקבוצת המשנה עם המספר הנמוך ביותר של אלמנטים, זה יבטיח מזעור רצפים באורך של פחות מ -3.

אַלגוֹרִיתְם

  1. האלמנט הראשון של המערך יוצר תמיד המשך חדש.
  2. חצו את המערך החל מאינדקס 1 (אינדקס מבוסס 0).
  3. בדוק אם יש המשך כלשהו שיכול להכיל את האלמנט הנוכחי, ניתן להוסיף אלמנט arr [i] לרצף שמסתיים ב- (arr [i] - 1).
  4. אם אין המשך שיכול להכיל את האלמנט הנוכחי, צרו המשך חדש.
  5. בחר אחרת ברצף בגודל מינימלי שיכול להכיל את האלמנט הנוכחי והוסף את הרכיב הנוכחי לרצף שנבחר.
  6. לאחר חציית המערך, בדוק אם יש המשך כלשהו באורך של פחות מ -3, אם כן, השב שקר, אחרת השב נכון.

קוד JAVA למערך מפוצל לתוצאות עוקבות

import java.util.ArrayList;

public class SplitTheArrayIntoConsecutievSubsequences {
    private static boolean isPossible(int[] arr) {
        // If the lenght of arr is less than 3, it is not possible to split the array
        if (arr == null || arr.length < 3) {
            return false;
        }
        int n = arr.length;

        // List of subsequences
        ArrayList<ArrayList<Integer>> al = new ArrayList<>();

        // First element always forms a new subsequence
        ArrayList<Integer> eles = new ArrayList<Integer>();
        eles.add(arr[0]);
        al.add(eles);

        // Traverse the array starting from index 1
        for (int i = 1; i < n; i++) {
            // Required position of subsequence that can accommodate the current element
            int pos = -1;
            // Size of required subsequence
            int size = -1;
            // Check if there is some subsequence that can accommodate the current element
            for (int j = 0; j < al.size(); j++) {
                // A subsequence ending at (arr[i] - 1) can accommodate the element arr[i]
                if (al.get(j).get(al.get(j).size() - 1) + 1 == arr[i]) {
                    if (pos == -1) {
                        pos = j;
                        size = al.get(j).size();
                    } else {
                        // Select the subsequence with minimum size
                        if (al.get(j).size() < size) {
                            pos = j;
                            size = al.get(j).size();
                        }
                    }
                }
            }

            // If there is no subsequence that can accommodate the current element
            // form a new subsequence
            if (pos == -1) {
                ArrayList<Integer> newAL = new ArrayList<>();
                newAL.add(arr[i]);
                al.add(newAL);
            } else {
                // else add it to the required subsequence
                al.get(pos).add(arr[i]);
            }
        }

        for (int i = 0; i < al.size(); i++) {
            // if there is some subsequence of length less than 3, return false
            if (al.get(i).size() < 3) {
                return false;
            }
        }
        // No subsequence of length less than 3, return true
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{1, 2, 3, 3, 4, 5};

        System.out.println(isPossible(arr1));

        // Example 2
        int arr2[] = new int[]{1, 2, 3, 3, 4, 4, 5, 5};

        System.out.println(isPossible(arr2));

        // Example 3
        int arr3[] = new int[]{1, 2, 3, 4, 4, 5};

        System.out.println(isPossible(arr3));
    }
}
true
true
false

קוד C ++ לפיצול מערך ברצף עוקב

#include<bits/stdc++.h> 
using namespace std;

bool isPossible(int *arr, int n) {
    if (n < 3) {
        return false;
    }
    
    // List of subsequences
    vector<vector<int>> v;
    
    // First element always forms a new subsequence
    vector<int> eles;
    eles.push_back(arr[0]);
    v.push_back(eles);
    
    // Traverse the array starting from index 1
    for (int i = 1; i < n; i++) {
        // Required position of subsequence that can accommodate the current element
        int pos = -1;
        // Size of required subsequence
        int size = -1;
        // Check if there is some subsequence that can accommodate the current element
        for (int j = 0; j < v.size(); j++) {
            // A subsequence ending at (arr[i] - 1) can accommodate the element arr[i]
            if (v[j][v[j].size() - 1] + 1 == arr[i]) {
                if (pos == -1) {
                    pos = j;
                    size = v[j].size();
                } else {
                    // Select the subsequence with minimum size
                    if (v[j].size() < size) {
                        size = v[j].size();
                        pos = j;
                    }
                }            
            }
        }
        
        // If there is no subsequence that can accommodate the current element
        // form a new subsequence
        if (pos == -1) {
            vector<int> newV;
            newV.push_back(arr[i]);
            v.push_back(newV);
        } else {
            v[pos].push_back(arr[i]);
        }
    }
    
    for (int i = 0; i < v.size(); i++) {
        if (v[i].size() < 3) {
            return false;
        }
    }
    return true;
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 3, 3, 4, 5};
    if(isPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    int arr2[] = {1, 2, 3, 3, 4, 4, 5, 5};
    if (isPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 3
    int arr3[] = {1, 2, 3, 4, 4, 5};
    if (isPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
        
    return 0;
}
true
true
false

ניתוח מורכבות

מורכבות זמן = O (n2)
מורכבות שטח = O (n)

גישה אופטימלית למערך מפוצל לתוצאות עוקבות

עבור אלמנט arr [i], או שהוא יכול ליצור המשך חדש או שניתן להוסיף אותו לרצף אחר שמסתיים ב- (arr [i] - 1), אם יש יותר משני אחד שיכולים להכיל arr [i], הוסף אותו להמשך האורך המינימלי.

רק שלושה סוגים של אורך המשך חשובים, כלומר, רצפים של אורך 1, אורך 2 ואורך הגדול משווה ל- 3, המסומנים כ- p1, c1, p2, c2, p3 ו- c3, כאשר p פירושו הקודם ו- c פירושו זרם.

עבור כל מספר ספר לראשונה את מספר המופעים שלו במערך, בדוק אם הוא יכול להתפשט על פני כל המשכים באורך 1 ו -2, אם הוא לא יכול, להחזיר שקר באופן מיידי, כי אם המספר הנוכחי לא יכול להאריך רצפים באורך 1 או 2, אף מספר לא יעשה כשממיין את המערך. אז יישארו כמה המשכים באורך 1 או 2 בסוף.

בחר את כל המשכי אורך 1 הממירים לרצפים של אורך 2, אורך 2 ממירים לאורך 3, והאלמנטים הנותרים מתווספים לרצפים באורך 3 או יותר, אם עדיין חלק מהאלמנטים אינם מופצים הם תורמים לרצפים באורך 1, אחרת רק האלמנטים התורמים לאורך 3 ומעלה מוסיפים לאורכים 3 האורך החדש.

בסוף, אם אין אורך 1 ואורכו 2 המשכים מחזירים נכון, אחרת החזירו שווא.

קוד JAVA

public class SplitArrayIntoConsecutiveSubsequences {
    private static boolean isPossible(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return false;
        }

        int p1 = 0, p2 = 0, p3 = 0;
        int c1 = 0, c2 = 0, c3 = 0;
        int i = 0;
        // prev denotes previous element
        // curr denotes current element
        int prev = 0, curr = 0;

        // Traverse the array
        while (i < n) {
            // Current becomes previous
            p1 = c1;
            p2 = c2;
            p3 = c3;

            prev = curr;
            curr = arr[i];

            int count = 0;
            // Count the frequency of current element
            while (i < n && arr[i] == curr) {
                i++;
                count++;
            }

            if (prev + 1 == curr) {
                // if element cannot be spread across subsequences of length 1 and 2
                if (count < p1 + p2) {
                    // return false immediately
                    return false;
                }
                // Update c1, c2, c3 as described
                c1 = Math.max(0, count - (p1 + p2 + p3));
                c2 = p1;
                c3 = p2 + Math.min(p3, count - (p1 + p2));
            } else {
                // this element cannot be spread across any subsequence
                if (p1 != 0 || p2 != 0) {
                    // if there is any subsequence of length 1 or 2
                    // return false immediately
                    return false;
                }
                // Update c1, c2, c3 as described
                c1 = count;
                c2 = 0;
                c3 = 0;
            }
        }

        // if there are no length 1 and length 2 subsequences return true, else return false
        return (c1 == 0 && c2 == 0);
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{1, 2, 3, 3, 4, 5};

        System.out.println(isPossible(arr1));

        // Example 2
        int arr2[] = new int[]{1, 2, 3, 3, 4, 4, 5, 5};

        System.out.println(isPossible(arr2));

        // Example 3
        int arr3[] = new int[]{1, 2, 3, 4, 4, 5};

        System.out.println(isPossible(arr3));
    }
}
true
true
false

קוד C ++

#include<bits/stdc++.h> 
using namespace std;

bool isPossible(int *arr, int n) {
    if (n < 3) {
        return false;
    }
    
    int p1 = 0, p2 = 0, p3 = 0;
    int c1 = 0, c2 = 0, c3 = 0;
    int i = 0;
    // prev denotes previous element
    // curr denotes current element
    int prev = 0, curr = 0;
    
    // Traverse the array
    while (i < n) {
        // Current becomes previous
        p1 = c1;
        p2 = c2;
        p3 = c3;
        
        prev = curr;
        curr = arr[i];
        
        int count = 0;
        // Count the frequency of current element
        while (i < n && arr[i] == curr) {
            i++;
            count++;
        }
        
        if (prev + 1 == curr) {
            // if element cannot be spread across subsequences of length 1 and 2
            if (count < p1 + p2) {
                // return false immediately
                return false;
            }
            // Update c1, c2, c3 as described
            c1 = std::max(0, count - (p1 + p2 + p3));
            c2 = p1;
            c3 = p2 + std::min(p3, count - (p1 + p2));
        } else {
            // this element cannot be spread across any subsequence
            if (p1 != 0 || p2 != 0) {
                // if there is any subsequence of length 1 or 2
                // return false immediately
                return false;
            }
            // Update c1, c2, c3 as described
            c1 = count;
            c2 = 0;
            c3 = 0;
        }
    }

    // if there are no length 1 and length 2 subsequences return true, else return false
    return (c1 == 0 && c2 == 0);
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 3, 3, 4, 5};
    if(isPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    int arr2[] = {1, 2, 3, 3, 4, 4, 5, 5};
    if (isPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 3
    int arr3[] = {1, 2, 3, 4, 4, 5};
    if (isPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
        
    return 0;
}
true
true
false

ניתוח מורכבות

מורכבות זמן = O (n)
מורכבות שטח = O (1)

הפניות