מספרים רצופים מקסימליים הנמצאים במערך


רמת קושי קַל
נשאל לעתים קרובות נאמן Adobe אמזון בעברית פורקיטים מאק
מערך בליל

הצהרת בעיה

נניח שיש לך מגוון של מספרים שלמים בגודל N. הבעיה "מקסימום מספרים עוקבים שנמצאים במערך" מבקשת לברר את המספר המרבי של מספרים עוקבים שיכולים להתפזר במערך.

דוגמה

arr[] = {2, 24, 30, 26, 99, 25}
3

הסבר: המספרים העוקבים הם ⇒ 24, 25, 26 (קבוצה של 3).

arr[] = { -8, 9 , -1, -6, -5}
2

הסבר: המספרים העוקבים הם ⇒ -6, -5 (קבוצה של 2).

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

1. Declare a set.
2. Do traversing of the array, and insert all the values of array into the Set.
3. Set output to 0.
4. Traverse the array from i=0, to i<n(length of the array).
  1. Check if Set contains the arr[i].
    1. If true, then pick the current array element and store it to temp.
  2. While Set contains the temp, repeatedly increases the values of temp.
  3. Find out the maximum between output and temp-arr[i] and store it into the output.
5. Return output.

הסבר

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

אנו הולכים להוסיף את כל ערכי המערך לסט. כי בהמשך אנו הולכים לבדוק גם מספרים עוקבים. נעבור שוב במערך, נבחר כל אלמנט ונבדוק אם ה מַפָּה יש את אותו arr [i], אם נכון אז נבחר את האלמנט הזה למשתנה זמני ולבדוק את זה שוב אם מפה מכילה את הטמפ 'הזה, אם נכון, ואז להגדיל את הערך של temp ב- 1 ואז לבדוק שוב, ו שוב הגדל אותו, ממשיך בזה עד למפה אין ערך מצטבר זה. כעת, כשאנחנו יוצאים מהלולאה הזו, נקבל את הערך המצטבר ביותר של אלמנט המערך הנוכחי שנמצא במפה, כמו כן אנו מגדילים אותו בספירה של 1, כך שיהיו גם מספרים עוקבים.

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

מספרים רצופים מקסימליים הנמצאים במערך

יישום

תוכנית C ++ לאיתור מספרים מרביים רצופים הנמצאים במערך

#include<iostream>
#include<unordered_set>

using namespace std;

int getMaxConsecutiveNumber(int arr[], int n)
{
    unordered_set<int> SET;
    for (int i = 0; i < n; i++)
        SET.insert(arr[i]);

    int output = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr[i] - 1) == SET.end())
        {
            int temp = arr[i];

            while (SET.find(temp) != SET.end())
                temp++;

            output = max(output, temp - arr[i]);
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 24, 30, 26, 99, 25 };
    int n = sizeof(arr) / sizeof(int);
    cout << "Largest Set found : "<<getMaxConsecutiveNumber(arr, n)<< endl;
    return 0;
}
Largest Set found : 3

תוכנית Java לאיתור מספרים מרביים רצופים הנמצאים במערך

import java.util.HashSet;

class LargestConsecutiveSet
{
    public static int getMaxConsecutiveNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
        }
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if(SET.contains(arr[i]))
            {
                int temp = arr[i];
                while (SET.contains(temp))
                    temp ++;

                output = Math.max(output, temp - arr[i]);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2, 24, 30, 26, 99, 25};
        int n = arr.length;
        System.out.println("Largest Set found : "+getMaxConsecutiveNumber(arr, n));
    }
}
Largest Set found : 3

ניתוח מורכבות למציאת מספרים מרביים רצופים הקיימים במערך

מורכבות זמן

O (n) איפה "N" הוא מספר האלמנטים במערך. מכיוון שהשתמשנו ב- HashSet, המאפשר פעולת הכנסה, מחיקה וחיפוש בזמן קבוע.

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך. אחסנו אלמנטים N בערכה ובכך מורכבות החלל הליניארית.

התייחסות