العنصر المفقود k-th في تسلسل متزايد غير موجود في تسلسل معين  


مستوى الصعوبة سهل
كثيرا ما يطلب في قلعة اكسبيديا القوات المسلحة البوروندية مجموعة الحقائق IBM مختبرات SAP
مجموعة مزيج البحث

توضح مشكلة "k-th مفقود عنصر في تسلسل متزايد غير موجود في تسلسل معين" أنه يتم منحك مصفوفتين. واحد منهم مرتب بترتيب تصاعدي وآخر عادي غير مصنف برقم k. أوجد العنصر المفقود k غير الموجود في التسلسل الطبيعي ولكنه موجود في مصفوفة تسلسل الترتيب المتزايد.

مثال  

العنصر المفقود k-th في تسلسل متزايد غير موجود في تسلسل معين

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

تفسير

الأرقام في التسلسل المتزايد غير الموجودة في الصفيف المحدد هي 0,8,14،XNUMX،XNUMX.

كth العدد المفقود ، أي 2nd الرقم هو 8

خوارزمية للعثور على العنصر المفقود k في تسلسل متزايد غير موجود في تسلسل معين  

  1. تعلن أ HashSet.
  2. ضع كل عناصر المصفوفة الثانية في HashSet.
  3. ضبط عداد في عداد المفقودين ل0.
  4. أثناء اجتياز المصفوفة المتسلسلة المتزايدة ، تحقق من:
    1. إذا كانت المجموعة لا تحتوي على أي عنصر من عناصر الصفيف المتسلسل
      1. قم بزيادة قيمة الحساب المفقود بمقدار 1.
      2. تحقق مما إذا كانت قيمة عداد المفقودين تساوي k.
        • إذا كان هذا صحيحًا ، فقم بإرجاع هذا الصفيف [i].
  5. خارج الحلقة ، قم بإرجاع -1.

تفسير

تحصل على مصفوفتين ورقم ك. أحد المصفوفتين عبارة عن تسلسل متزايد والآخر هو تسلسل عادي غير مصنف. تنص عبارة المشكلة على أنه يجب عليك العثور على العنصر المفقود k في مصفوفة التسلسل التي تم فرزها والتي لا توجد في المصفوفة التي لم يتم فرزها.

انظر أيضا
أوجد أكبر d في المصفوفة بحيث تكون a + b + c = d

سنستخدم مجموعة لهذا الغرض. سنقوم باجتياز المصفوفة الثانية ب[] وأدخل كل قيمته في المجموعة. هذا لأنه يمكننا التحقق منه لاحقًا ومقارنة المجموعة بالمصفوفة الأولى أ[]. أثناء عبور المصفوفة [] ، إذا كانت المجموعة لا تحتوي على تلك القيمة الخاصة للمصفوفة [i]. نزيد من قيمة عداد في عداد المفقودين بمقدار 1 وتحقق في الوقت نفسه مما إذا كان الحساب المفقود يساوي الرقم المحدد ك. إذا كان الأمر كذلك ، فيمكننا إرجاع عنصر المصفوفة الأولى.

دعونا نفكر في مثال ونفهم هذا.

مثال

صفيف أ [] = [0 ، 2 ، 4 ، 6 ، 8 ، 10 ، 12 ، 14]

ب [] = [4 ، 10 ، 6 ، 12 ، 2]

ك = 2

وفقًا للخوارزمية ، نحتاج إلى وضع عناصر المصفوفة b [] في مجموعة. سنفعل ذلك عن طريق اجتياز المصفوفة b [].

ستصبح مجموعتنا {4 ، 10 ، 6 ، 12 ، 2}

نحتاج إلى اجتياز عناصر المصفوفة a [] والتحقق مما إذا كانت المجموعة لا تحتوي على عنصر arr [i] ،

أنا = 0 ، arr [i] = 0

لا تحتوي المجموعة على ذلك ، لذا ستزيد في عداد المفقودين = عدد المفقودين + 1

MissCount = 1 ، تحقق مما إذا كان عداد مفقود == k ، فهو خطأ.

أنا = 1 ، arr [i] = 2

المجموعة تحتوي على تلك القيمة "2" ، لذا فهي لا تفعل شيئًا.

أنا = 2 ، arr [i] = 4

المجموعة تحتوي على تلك القيمة "4" ، لذا فهي لا تفعل شيئًا.

أنا = 3 ، arr [i] = 6

المجموعة تحتوي على تلك القيمة "6" ، لذا فهي لا تفعل شيئًا.

أنا = 4 ، arr [i] = 8

لا تحتوي المجموعة على 8 ، لذلك ستزيد في عداد المفقودين = عدد المفقودين + 1

MissCount = 2 ، تحقق مما إذا كان missingCount == k ، هذا صحيح ، لذا سيعيد arr [i] الذي هو '8' ،

سيصبح الناتج 8.

انظر أيضا
نطاق زمني ثابت يضيف عملية على مصفوفة

رمز  

كود C ++ للعثور على العنصر المفقود k-th في تسلسل متزايد غير موجود في تسلسل معين

#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 للعثور على العنصر المفقود k-th في تسلسل متزايد غير موجود في تسلسل معين

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" هي طول array1 و array2. نظرًا لأننا اجتزنا جميع العناصر من كلا المصفوفتين. التعقيد الزمني خطي.

تعقيد الفضاء

على 2) أين "n2" هو طول array2. نظرًا لأننا قمنا بتخزين عناصر المصفوفة الثانية فقط في HashSet ، فإن المساحة المطلوبة تكون خطية أيضًا.

انظر أيضا
تجزئة الوقواق