ק-טה פעלנדיק עלעמענט אין ינקריסינג סיקוואַנס וואָס איז נישט פאָרשטעלן אין אַ געגעבן סיקוואַנס  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין ציטאַדעל עקספּעדיאַ Fab פאַקסעט יבם SAP לאַבס
מענגע האַש שאַרף

די פּראָבלעם "ק-טה פעלנדיק עלעמענט אין ינקריסינג סיקוואַנס וואָס איז נישט פאָרשטעלן אין אַ געגעבן סיקוואַנס" שטאַטן אַז איר האָט צוויי ערייז. איינער פון זיי איז עריינדזשד אין אַסענדינג סדר און אן אנדער נאָרמאַל ונסאָרטעד מענגע מיט נומער ק. געפֿינען די קטה פעלנדיק עלעמענט וואָס איז נישט פאָרשטעלן אין נאָרמאַל סיקוואַנס אָבער איז פאָרשטעלן אין ינקריסינג סדר סיקוואַנס מענגע.

בייַשפּיל  

ק-טה פעלנדיק עלעמענט אין ינקריסינג סיקוואַנס וואָס איז נישט פאָרשטעלן אין אַ געגעבן סיקוואַנס

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

דערקלערונג

די נומערן אין די ינקריסינג סיקוואַנס וואָס זענען נישט פאָרשטעלן אין די געגעבן מענגע זענען 0,8,14.

די קth פעלנדיק נומער הייסט, 2nd נומער איז 8

אַלגערידאַם צו געפֿינען ק-טה פעלנדיק עלעמענט אין ינקריסינג סיקוואַנס וואָס איז ניט פאָרשטעלן אין אַ געגעבן סיקוואַנס  

  1. דערקלערן א האַשסעט.
  2. שטעלן אַלע די יסודות פון די רגע מענגע אין האַשסעט.
  3. שטעלן פעלנדיק קאָונט צו קסנומקס.
  4. בשעת דורכפאָר די ינקריסינג סאַקווענטשאַל מענגע, טשעק:
    1. אויב אַ סכום כּולל קיין פון די סאַקווענטשאַל מענגע עלעמענט
      1. פאַרגרעסערן די פעלנדיק קאָונט ווערט מיט 1.
      2. קאָנטראָלירן אויב פעלנדיק צאָלונג ווערט איז ק.
        • אויב אמת, צוריקקומען די מענגע [i].
  5. אַרויס פון די שלייף, צוריקקומען -1.

דערקלערונג

איר האָט צוויי ערייז און אַ נומער קיי. איינער פון די צוויי ערייז איז אַ ינקריסינג סיקוואַנס און די אנדערע איז אַ נאָרמאַל ונסאָרטעד סיקוואַנס. די פּראָבלעם ויסזאָגונג זאגט אַז איר דאַרפֿן צו געפֿינען די Kth פעלנדיק עלעמענט אין די סאָרטעד סיקוואַנס מענגע וואָס איז נישט פאָרשטעלן אין די אַנסאָרטאַד מענגע.

זע אויך
געפֿינען די גרעסטע ד אין אַררייַ אַזאַ אַז a + b + c = ד

מיר וועלן נוצן אַ סכום פֿאַר דעם. מיר וועלן אַריבער די רגע מענגע b [] און אַרייַן אַלע די ווערט אין דעם גאַנג. דאָס איז ווייַל מיר קענען קאָנטראָלירן עס שפּעטער און פאַרגלייכן דעם גאַנג מיט דער ערשטער מענגע אַ []. בשעת דורכפאָר די מענגע אַ [], אויב די סכום כּולל נישט דעם באַזונדער ווערט פון מענגע אַ [איך]. מיר פאַרגרעסערן די ווערט פון פעלנדיק קאָונט דורך 1 און קאָנטראָלירן סיימאַלטייניאַסלי אויב פעלנדיק צאָלונג איז גלייַך צו די געגעבן נומער k. אויב דאָס, מיר קענען צוריקקומען דעם עלעמענט פון דער ערשטער מענגע.

זאל אונדז באַטראַכטן אַ בייַשפּיל און פֿאַרשטיין דעם.

בייַשפּיל

מענגע a [] = [0, 2, 4, 6, 8, 10, 12, 14]

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

k = 2

לויט צו אַלגערידאַם, מיר דאַרפֿן צו שטעלן די ברייטער [b] עלעמענטן. מיר וועלן טאָן דאָס דורך אַריבער די מענגע ב [].

אונדזער גאַנג וועט ווערן {4, 10, 6, 12, 2}

מיר דאַרפֿן צו דורכגיין די [] עלעמענטן פון די מענגע און קאָנטראָלירן אויב שטעלן טוט נישט אַנטהאַלטן אַרר [i] עלעמענט,

איך = 0, אַרר [איך] = 0

שטעלן טוט ניט אַנטהאַלטן עס אַזוי עס וועט פאַרגרעסערן פעלנדיק קאָונט = פעלנדיק קאָונט + 1

פעלנדיק קאָונט = 1, טשעק אויב פעלנדיק קאָונט == ק, עס איז פאַלש.

איך = 1, אַרר [איך] = 2

שטעלן כּולל די ווערט '2', אַזוי עס גאָרנישט.

איך = 2, אַרר [איך] = 4

שטעלן כּולל די ווערט '4', אַזוי עס גאָרנישט.

איך = 3, אַרר [איך] = 6

שטעלן כּולל די ווערט '6', אַזוי עס גאָרנישט.

איך = 4, אַרר [איך] = 8

שטעלן טוט ניט אַנטהאַלטן 8, אַזוי עס וועט פאַרגרעסערן פעלנדיק קאָונט = פעלנדיק קאָונט + 1

פעלנדיק קאָונט = 2, טשעק אויב פעלנדיק קאָונט == ק, עס איז אמת אַזוי עס וועט צוריקקומען אַרר [איך] וואָס איז '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

דזשאַוואַ קאָד צו געפֿינען קיי-טה פעלנדיק עלעמענט אין ינקריסינג סיקוואַנס וואָס איז ניט פאָרשטעלן אין אַ געגעבן סיקוואַנס

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

קאַמפּלעקסיטי אַנאַליסיס  

צייט קאַמפּלעקסיטי

אָ (n1 + n2) ווו “N1” און “N2” זענען לענג פון מענגע 1 און אַרע 2. זינט מיר האָבן דורכגעקאָכט אַלע עלעמענטן פֿון ביידע ערייז. די צייט קאַמפּלעקסיטי איז לינעאַר.

ספעיס קאַמפּלעקסיטי

אָ (N2) ווו “N2” איז די לענג פון מענגע 2. ווייַל מיר האָבן בלויז סטאָרד די עלעמענטן פון די רגע מענגע אין די האַשסעט, די פארלאנגט פּלאַץ איז אויך לינעאַר.

זע אויך
קוקו האַשינג