ক্রমবর্ধমান ক্রমানুসারে কে-থেম অনুপস্থিত উপাদান যা প্রদত্ত অনুক্রমের মধ্যে উপস্থিত নেই


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় দুর্গ এক্সপিডিয়া প্রভূত ফ্যাক্সেট আইবিএম এসএপি ল্যাব
বিন্যাস কাটা খোঁজ

সমস্যাটি "ক্রমবর্ধমান ক্রমানুসারে কে-থেম অনুপস্থিত উপাদান যা প্রদত্ত ক্রমটিতে উপস্থিত নেই" আপনাকে উল্লেখ করে যে আপনাকে দুটি অ্যারে দেওয়া হয়েছে। এর মধ্যে একটি ক্রমবর্ধমান ক্রমে সজ্জিত এবং অন্য একটি সাধারণ সংখ্যা সহ কে। কেএইচটি অনুপস্থিত উপাদানটি সন্ধান করুন যা সাধারণ ক্রমগুলিতে উপস্থিত না তবে ক্রম ক্রমের ক্রমবর্ধমান উপস্থিত রয়েছে।

উদাহরণ

ক্রমবর্ধমান ক্রমানুসারে কে-থেম অনুপস্থিত উপাদান যা প্রদত্ত অনুক্রমের মধ্যে উপস্থিত নেই

[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. সেট অনুপস্থিত হিসাব 0 তে
  4. ক্রমবর্ধমান ক্রমক্রমিক অ্যারে অনুসরণ করার সময়, চেক করুন:
    1. যদি কোনও সেটটিতে অনুক্রমিক অ্যারে উপাদানগুলির কোনও থাকে না
      1. গুমের হিসাবের মান 1 দ্বারা বাড়ান।
      2. অনুপস্থিত হিসাবের মান k এর সমান কিনা তা পরীক্ষা করে দেখুন।
        • সত্য হলে, সেই অ্যারেটি ফিরিয়ে দিন [i]।
  5. লুপ থেকে, ফিরে -1।

ব্যাখ্যা

আপনাকে দুটি অ্যারে এবং একটি নম্বর কে দেওয়া হবে। দুটি অ্যারেগুলির একটি হ'ল একটি ক্রমবর্ধমান ক্রম এবং অন্যটি হ'ল একটি সাধারণ অনিবৃদ্ধ ক্রম। সমস্যা বিবৃতিতে বলা হয়েছে যে আপনি বাছাই করা ক্রম অ্যারেতে কাঠের অনুপস্থিত উপাদানটি সন্ধান করতে হবে যা মীমাংসিত অ্যারেটিতে নেই।

আমরা এই জন্য একটি সেট ব্যবহার করতে যাচ্ছি। আমরা দ্বিতীয় অ্যারে অতিক্রম করতে যাচ্ছি খ [] এবং সেটির সমস্ত মান .োকান। কারণ এটি আমরা পরে যাচাই করতে পারি এবং সেটটিকে প্রথম অ্যারের সাথে তুলনা করতে পারি একটি []। অ্যারেটি ট্র্যাভার করার সময়, যদি সেটটিতে অ্যারের একটি নির্দিষ্ট মান না থাকে [i]। আমরা এর মান বৃদ্ধি করি অনুপস্থিত হিসাব 1 দ্বারা এবং একই সাথে পরীক্ষা করুন যে অনুপস্থিত হিসাবটি প্রদত্ত সংখ্যার কে এর সমান হয় কিনা। যদি এটি হয় তবে আমরা প্রথম অ্যারের সেই উপাদানটি ফিরিয়ে দিতে পারি।

আসুন একটি উদাহরণ বিবেচনা করুন এবং এটি বুঝতে পারি।

উদাহরণ

অ্যারে এ [] = [0, 2, 4, 6, 8, 10, 12, 14]

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

ট = 2

অ্যালগরিদম অনুসারে, আমাদের অ্যারে বি [] উপাদানগুলিকে সেট করতে হবে। আমরা অ্যারে বি [] কে অনুসরণ করে এটি করব।

আমাদের সেটটি {4, 10, 6, 12, 2 become হয়ে যাবে

আমাদের অ্যারেটিকে একটি [] উপাদান অতিক্রম করতে হবে এবং সেটটিতে আরার [i] উপাদান নেই কিনা তা পরীক্ষা করতে হবে,

i = 0, এআর [i] = 0

সেটটিতে এটি থাকে না তাই এটি মিসিংকাউন্ট = অনুপস্থিত অ্যাকাউন্ট +1 বাড়িয়ে তুলবে

অনুপস্থিত অ্যাকাউন্ট = 1, অনুপস্থিত হিসাব == কে কিনা পরীক্ষা করুন, এটি মিথ্যা।

i = 1, এআর [i] = 2

সেটের মান '2' রয়েছে, তাই এটি কিছুই করে না।

i = 2, এআর [i] = 4

সেটের মান '4' রয়েছে, তাই এটি কিছুই করে না।

i = 3, এআর [i] = 6

সেটের মান '6' রয়েছে, তাই এটি কিছুই করে না।

i = 4, এআর [i] = 8

সেটটিতে 8 টি থাকে না, সুতরাং এটি মিসিংকাউন্ট = অনুপস্থিত অ্যাকাউন্ট +1 বৃদ্ধি করবে

অনুপস্থিত গণনা = ২, অনুপস্থিত হিসাব == কে কিনা তা পরীক্ষা করে দেখুন, এটি সত্য তাই এটি arr ফিরে আসবে [i] যা '2',

আউটপুট 8 হয়ে যাবে।

কোড

ক্রমবর্ধমান ক্রমের কে-থেম অনুপস্থিত উপাদানগুলি সন্ধানের জন্য সি ++ কোড যা প্রদত্ত অনুক্রমের মধ্যে উপস্থিত নেই

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন 1 + এন 2) কোথায় "এন 1" এবং "এন 2" অ্যারে 1 এবং অ্যারে 2 এর দৈর্ঘ্য। যেহেতু আমরা উভয় অ্যারে থেকে সমস্ত উপাদানকে সরিয়ে নিয়েছি। সময় জটিলতা রৈখিক।

স্পেস জটিলতা ity

ও (এন 2) কোথায় "এন 2" অ্যারে 2 এর দৈর্ঘ্য। যেহেতু আমরা কেবল দ্বিতীয় অ্যারের উপাদানগুলি হ্যাশসেটে সঞ্চিত করেছি, প্রয়োজনীয় স্থানটিও রৈখিক।