מצא אלמנטים חסרים בטווח


רמת קושי קַל
נשאל לעתים קרובות מסירה גריי אורנג ' לינקדין נגארו לפעול סינופסיס
בליל לארסן וטוברו מִיוּן

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

דוגמה

מצא אלמנטים חסרים בטווח

arr[] = [1, 3, 5, 7, 8, 9]

low=1 high = 10
2, 4, 6, 10

הסבר

אלה המספרים החסרים במערך בטווח הנתון כגבוה ונמוך, כלומר 1 ו -10.

arr[] = [2, 3, 7, 8]

low=1 high = 9
1, 4, 5, 6, 9

הסבר

אלה המספרים החסרים במערך בטווח הנתון כגבוה ונמוך, כלומר 1 ו -10.

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

  1. הכריז א סט.
  2. חצו את המערך והכניסו את כל האלמנטים לסט.
  3. בעוד ש- "i" שווה לנמוך ו- "i" שווה לגבוה.
    • אם סט אינו מכיל "i".
      • הדפיס 'אני'.

הסבר

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

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

arr [] = {2, 3, 7, 8} נמוך = 1, גבוה = 9

עלינו לחצות את המערך ולהכניס את כל האלמנטים של המערך לסט. הסט שלנו יהפוך

סט = [2,3,7,8]

בלולאה שאותחילה אני ל- נמוך והלולאה פועלת עד גבוהה, פירוש הדבר ש- 'אני' שווה ל- low = 1 וגבוה = 9

i = 1, אם הסט אינו מכיל i, מדפיס 1

[1]

i = 2, לסט יש ערך '2' ולא עושה כלום.

i = 3, לסט יש ערך '3' ולא עושה כלום.

i = 4, אם הסט אינו מכיל i, מדפיס 4

[1, 4]

i = 5, אם הסט אינו מכיל i, מדפיס 5

[1, 4, 5]

i = 6, אם הסט אינו מכיל i, מדפיס 6

[1, 4, 5, 6]

i = 7, לסט יש ערך '7' ולא עושה כלום.

i = 8, לסט יש ערך '8' ולא עושה כלום.

i = 9, אם הסט אינו מכיל i, מדפיס 1

[1, 4, 5, 6, 9]

התפוקה שלנו תהפוך ל: [1, 4, 5, 6, 9]

קופונים

קוד C ++ כדי למצוא אלמנטים חסרים בטווח

#include <unordered_set>
#include<iostream>

using namespace std;

void getMissingElements(int arr[], int n, int low, int high)
{
    unordered_set<int> myset;
    for (int i = 0; i < n; i++)
        myset.insert(arr[i]);

    for (int x = low; x <= high; x++)
        if (myset.find(x) == myset.end())
            cout << x << " ";
}
int main()
{
    int arr[] = { 2,3,7,8 };
    int low = 1, high = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    getMissingElements(arr, n, low, high);
    return 0;
}
1 4 5 6 9

קוד Java כדי למצוא אלמנטים חסרים בטווח

import java.util.HashSet;

class RangeMissingElements
{
    public static void getMissingElements(int arr[], int low, int high)
    {
        HashSet<Integer> myset = new HashSet<>();

        for (int i = 0; i < arr.length; i++)
        {
            myset.add(arr[i]);
        }

        for (int i = low; i <= high; i++)
        {
            if (!myset.contains(i))
            {
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,7,8};
        int low = 1, high = 9;
        getMissingElements(arr, low, high);
    }
}
1 4 5 6 9

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

מורכבות זמן

O (n + (גבוה-נמוך + 1)) איפה "N" הוא מספר האלמנטים הקיימים במערך, "גָבוֹהַ" ו "נָמוּך" הוא הקלט המסופק.

מורכבות בחלל

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