கொடுக்கப்பட்ட வரிசையில் இல்லாத அதிகரிக்கும் வரிசையில் k-வது உறுப்பு காணவில்லை


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது சிட்டாடல் Expedia ஃபேப் உண்மை ஐபிஎம் SAP ஆய்வகங்கள்
அணி ஹாஷ் தேடி

"கொடுக்கப்பட்ட வரிசையில் இல்லாத அதிகரிக்கும் அதிகரிக்கும் வரிசையில் k-th காணாமல் போன உறுப்பு" சிக்கல் உங்களுக்கு இரண்டு வரிசைகள் வழங்கப்படுவதாகக் கூறுகிறது. அவற்றில் ஒன்று ஏறுவரிசையில் அமைக்கப்பட்டுள்ளது மற்றும் மற்றொரு சாதாரண வரிசைப்படுத்தப்படாத வரிசை எண் k உடன் அமைக்கப்பட்டுள்ளது. சாதாரண வரிசையில் இல்லாத, ஆனால் வரிசை வரிசை வரிசையில் அதிகரிப்பதில் இருக்கும் kth விடுபட்ட உறுப்பைக் கண்டறியவும்.

உதாரணமாக

கொடுக்கப்பட்ட வரிசையில் இல்லாத அதிகரிக்கும் வரிசையில் k-வது உறுப்பு காணவில்லை

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

விளக்கம்

கொடுக்கப்பட்ட வரிசையில் இல்லாத அதிகரிக்கும் வரிசையில் உள்ள எண்கள் 0,8,14 ஆகும்.

தி கேth காணாமல் போன எண் அதாவது 2nd எண் 8 ஆகும்

கொடுக்கப்பட்ட வரிசையில் இல்லாத அதிகரிக்கும் வரிசையில் k-வது விடுபட்ட உறுப்பைக் கண்டறிய வழிமுறை

  1. ஒரு அறிவிக்கவும் ஹாஷ்செட்.
  2. இரண்டாவது வரிசையின் அனைத்து கூறுகளையும் ஹாஷ்செட்டில் வைக்கவும்.
  3. தொகுப்பு காணாமல் போன எண்ணிக்கை 0 வரை.
  4. அதிகரித்து வரும் வரிசை வரிசையை கடந்து செல்லும்போது, ​​சரிபார்க்கவும்:
    1. ஒரு தொகுப்பில் தொடர்ச்சியான வரிசை உறுப்பு எதுவும் இல்லை என்றால்
      1. விடுபட்ட எண்ணிக்கையின் மதிப்பை 1 ஆல் அதிகரிக்கவும்.
      2. காணாமல் போன எண்ணிக்கை மதிப்பு k க்கு சமமாக இருக்கிறதா என்று சோதிக்கவும்.
        • உண்மை என்றால், அந்த வரிசையை திருப்பி விடுங்கள் [i].
  5. வளையத்திற்கு வெளியே, திரும்ப -1.

விளக்கம்

உங்களுக்கு இரண்டு வரிசைகள் மற்றும் ஒரு எண் k வழங்கப்படுகிறது. இரண்டு வரிசைகளில் ஒன்று அதிகரிக்கும் வரிசை மற்றும் மற்றொன்று சாதாரண வரிசைப்படுத்தப்படாத வரிசை. வரிசைப்படுத்தப்பட்ட வரிசை வரிசையில் இல்லாத kth உறுப்பைக் கண்டுபிடிக்க வேண்டும் என்று சிக்கல் அறிக்கை கூறுகிறது.

இதற்காக ஒரு தொகுப்பைப் பயன்படுத்தப் போகிறோம். நாம் இரண்டாவது வரிசையை கடக்கப் போகிறோம் b [] அதன் மதிப்பு அனைத்தையும் தொகுப்பில் செருகவும். ஏனென்றால், பின்னர் அதைச் சரிபார்த்து, தொகுப்பை முதல் வரிசையுடன் ஒப்பிடலாம் 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 become ஆக மாறும்

நாம் வரிசைக்கு ஒரு [] உறுப்புகளைக் கடந்து செல்ல வேண்டும், மேலும் தொகுப்பில் அர் [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 என்பதைச் சரிபார்க்கவும், அது உண்மைதான், எனவே அது '8' என்று வரும் [i]

வெளியீடு 8 ஆக மாறும்.

குறியீடு

கொடுக்கப்பட்ட வரிசையில் இல்லாத அதிகரிக்கும் வரிசையில் k-வது விடுபட்ட உறுப்பைக் கண்டுபிடிக்க சி ++ குறியீடு

#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

கொடுக்கப்பட்ட வரிசையில் இல்லாத அதிகரிக்கும் வரிசையில் k-வது விடுபட்ட உறுப்பைக் கண்டுபிடிக்க ஜாவா குறியீடு

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 இன் நீளம். இரண்டாவது வரிசையின் கூறுகளை மட்டுமே நாங்கள் ஹாஷ்செட்டில் சேமித்து வைத்திருப்பதால், தேவையான இடமும் நேரியல் ஆகும்.