વધતા ક્રમમાં કે-મી ગુમ તત્વ જે આપેલ અનુક્રમમાં હાજર નથી


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે સિટાડેલ એક્સપેડિયા ફેબ ફેક્ટસેટ IBM એસએપી લેબ્સ
અરે હેશ શોધી રહ્યું છે

સમસ્યા "વધતા જતા ક્રમમાં કે-થાઇ ગુમ તત્વ જે આપેલ ક્રમમાં હાજર નથી" જણાવે છે કે તમને બે એરે આપવામાં આવે છે. તેમાંથી એક ચડતા ક્રમમાં ગોઠવાયેલ છે અને બીજું સામાન્ય કે સાથે સંખ્યામાં કે. Kth ગુમ તત્વ શોધો જે સામાન્ય ક્રમમાં હાજર નથી પરંતુ વધતા ક્રમમાં ક્રમમાં ક્રમમાં એરે હાજર છે.

ઉદાહરણ

વધતા ક્રમમાં કે-મી ગુમ તત્વ જે આપેલ અનુક્રમમાં હાજર નથી

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

સમજૂતી

આપેલા એરેમાં હાજર ન હોય તેવા વધતા ક્રમમાં સંખ્યાઓ 0,8,14 છે.

આ કેth ગુમ સંખ્યા એટલે કે, 2nd સંખ્યા 8 છે

વધતા ક્રમમાં કે-th ગુમ તત્વ શોધવા માટે એલ્ગોરિધમ જે આપેલ ક્રમમાં હાજર નથી

  1. ઘોષણા કરો એ હેશસેટ.
  2. બીજા એરેના બધા ઘટકોને હેશસેટમાં મૂકો.
  3. સેટ ગુમ થયેલ એકાઉન્ટ 0 પર.
  4. વધતી ક્રમશક્તિ એરેને પસાર કરતી વખતે, તપાસો:
    1. જો સમૂહમાં કોઈપણ અનુક્રમિત એરે તત્વ શામેલ નથી
      1. ગુમ થયેલ ખાતાના મૂલ્યમાં 1 વધારો.
      2. તપાસ કરો કે ગુમ થયેલ ગણતરીની કિંમત k ની બરાબર છે કે નહીં.
        • જો સાચું હોય, તો તે એરે પાછો [i].
  5. લૂપમાંથી, વળતર -1.

સમજૂતી

તમને બે એરે અને નંબર કે આપવામાં આવે છે. બે એરેમાંનો એક વધતો ક્રમ છે અને બીજો એક એ સામાન્ય અનસોર્ટેડ ક્રમ છે. સમસ્યાનું નિવેદન કહે છે કે તમારે સ sequર્ટ કરેલ ક્રમ એરેમાં kth ગુમ થયેલ તત્વ શોધી કા toવું પડશે જે સ theર્ટ કરેલા એરેમાં નથી.

આ માટે આપણે સેટનો ઉપયોગ કરીશું. આપણે બીજી એરેને પસાર કરીશું બી [] અને તેની બધી કિંમત સેટમાં દાખલ કરો. આ તે છે કારણ કે આપણે તેને પછીથી ચકાસીએ અને સેટને પ્રથમ એરે સાથે સરખાવી શકીએ એક []. એરેને ટ્રversવર્સ કરતી વખતે [], જો સેટમાં એરે એ [i] નું વિશિષ્ટ મૂલ્ય શામેલ નથી. અમે ની કિંમત વધારીએ છીએ ગુમ થયેલ એકાઉન્ટ 1 દ્વારા અને એક સાથે તપાસો કે શું ગુમ થયેલ ખાતું આપેલ નંબર k ની બરાબર થાય છે. જો તે થાય, તો આપણે પહેલા એરેના એલિમેન્ટ પાછા આપી શકીએ છીએ.

ચાલો આપણે એક ઉદાહરણ ધ્યાનમાં લઈએ અને આ સમજીએ.

ઉદાહરણ

એરે એ [] = [0, 2, 4, 6, 8, 10, 12, 14]

બી [] = [4, 10, 6, 12, 2]

કે = 2

એલ્ગોરિધમ મુજબ, આપણે એરે બી [] એલિમેન્ટ્સને સેટમાં મૂકવાની જરૂર છે. આપણે આ એરે બી [] ને ટ્રingવર્સ કરીને કરીશું.

અમારો સમૂહ {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 વધારશે

ગુમ થયેલ કાઉન્ટ = 2, તપાસો કે ગુમ થયેલ ગણતરી == કે, તે સાચું છે તેથી તે એઆર પરત આવશે [i] તે '8' છે,

આઉટપુટ 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

વધતા ક્રમમાં કે-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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન 1 + એન 2) જ્યાં “એન 1” અને “એન 2” એરે 1 અને એરે 2 ની લંબાઈ છે. કારણ કે અમે બંને એરેમાંથી બધા તત્વો કાed્યા છે. સમયની જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (એન 2) જ્યાં “એન 2” એરે 2 ની લંબાઈ છે. કારણ કે આપણે ફક્ત બીજા એરેના તત્વોને હેશસેટમાં સંગ્રહિત કર્યા છે, તેથી જરૂરી જગ્યા પણ રેખીય છે.