אלמנט חסר חמישי ברצף הולך וגדל שאינו קיים ברצף נתון


רמת קושי קַל
נשאל לעתים קרובות מצודה Expedia פאב סט עובדות יבמ מעבדות SAP
מערך בליל חיפוש

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

דוגמה

אלמנט חסר חמישי ברצף הולך וגדל שאינו קיים ברצף נתון

[0, 2, 4, 6, 8, 10, 12, 14]
[4, 10, 6, 12, 2 ]
k=2
8

הסבר

המספרים ברצף הגדל שאינם קיימים במערך הנתון הם 0,8,14.

הקth מספר חסר כלומר, 2nd המספר הוא 8

אלגוריתם לאיתור אלמנט חסר חמישי ברצף הגדל שאינו קיים ברצף נתון

  1. הכריז א HashSet.
  2. הכנס את כל האלמנטים של המערך השני ל- HashSet.
  3. לקבוע חסר מספר אל 0.
  4. בזמן חציית המערך הרציף ההולך וגדל, בדוק:
    1. אם קבוצה אינה מכילה אלמנט מערך רציף
      1. הגדל את ערך ה- Counting חסר ב- 1.
      2. בדוק אם חסר ערך הספירה שווה ל- k.
        • אם נכון, החזר את המערך [i].
  5. מחוץ לולאה, חזור -1.

הסבר

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

אנו הולכים להשתמש בערכה לשם כך. אנו הולכים לחצות את המערך השני ב [] והכנס את כל הערך שלו לסט. הסיבה לכך היא שאנחנו יכולים לבדוק את זה מאוחר יותר ולהשוות את הסט עם המערך הראשון א[]. תוך כדי חציית המערך a [], אם הסט אינו מכיל את אותו ערך מסוים של מערך a [i]. אנו מעלים את הערך של חסר מספר על ידי 1 ובו זמנית לבדוק אם חסר המספר הופך להיות שווה למספר הנתון k. אם כן, נוכל להחזיר את האלמנט הזה של המערך הראשון.

הבה נבחן דוגמה ונבין זאת.

דוגמה

מערך a [] = [0, 2, 4, 6, 8, 10, 12, 14]

b [] = [4, 10, 6, 12, 2]

k = 2

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

הסט שלנו יהפוך ל- {4, 10, 6, 12, 2}

עלינו לחצות את מערך אלמנטים [] ולבדוק אם הסט אינו מכיל אלמנט arr [i],

i = 0, arr [i] = 0

הערכה אינה מכילה אותה ולכן היא תגדיל את חסר הספירה = חסר הספירה + 1

missingCount = 1, בדוק אם missingCount == k, זה שקר.

i = 1, arr [i] = 2

הסט מכיל את הערך '2', ולכן הוא לא עושה דבר.

i = 2, arr [i] = 4

הסט מכיל את הערך '4', ולכן הוא לא עושה דבר.

i = 3, arr [i] = 6

הסט מכיל את הערך '6', ולכן הוא לא עושה דבר.

i = 4, arr [i] = 8

הערכה אינה מכילה 8, כך שהיא תגדיל את חסר הספירה = חסר הספירה + 1

missingCount = 2, בדוק אם missingCount == k, זה נכון אז זה יחזיר את arr [i] כלומר '8',

התפוקה תהפוך ל -8.

קופונים

קוד C ++ לאיתור אלמנט חסר חמישי ברצף הולך וגדל שאינו קיים ברצף נתון

#include <unordered_set>
#include<iostream>

using namespace std;
int find(int A[], int B[], int k, int l1, int l2)
{
  unordered_set<int> myset;
  for (int i = 0; i < l2; i++)
    myset.insert(B[i]);

  int missingCount = 0;
  for (int i = 0; i < l1; i++) {
    if (myset.find(A[i]) == myset.end())
      missingCount++;
    if (missingCount == k)
      return A[i];
  }

  return -1;
}
int main()
{
    int a[] = { 0, 2, 4, 6, 8, 10, 12, 14};
    int b[] = { 4, 10, 6, 12, 2 };

  int l1 = sizeof(a) / sizeof(a[0]);
  int l2 = sizeof(b) / sizeof(b[0]);

  int k = 2;
  cout << find(a, b, k, l1, l2);
  return 0;
}
8

קוד Java למציאת אלמנט חסר חמישי ברצף הגדל שאינו קיים ברצף נתון

import java.util.LinkedHashSet;

class kthMissingElement
{
    public static int getMissingElement(int A[], int B[], int k, int l1, int l2)
    {
        LinkedHashSet<Integer> hashset = new LinkedHashSet<>();
        for (int i = 0; i < l2; i++)
            hashset.add(B[i]);

        int missingCount = 0;
        for (int i = 0; i < l1; i++)
        {
            if(!hashset.contains(A[i]) )
                missingCount++;
            if (missingCount == k)
                return A[i];
        }

        return -1;
    }
    public static void main(String[] args)
    {
        int a[] = { 0, 2, 4, 6, 8, 10, 12, 14};
        int b[] = { 4, 10, 6, 12, 2 };
        int l1 = a.length;
        int l2 = b.length;

        int k = 2;
        System.out.println(getMissingElement(a, b, k, l1, l2));
    }
}
8

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

מורכבות זמן

O (n1 + n2) איפה "N1" ו "N2" הם אורך מערך 1 ומערך 2. מכיוון שעברנו את כל האלמנטים משני המערכים. מורכבות הזמן היא לינארית.

מורכבות בחלל

O (n2) איפה "N2" הוא אורך המערך 2. מכיוון שאחסנו רק את האלמנטים של המערך השני ב- HashSet, השטח הנדרש הוא גם ליניארי.