දී ඇති අනුක්‍රමයක නොපවතින අනුක්‍රමය වැඩි කිරීමේ k-th මූලද්‍රව්‍යය


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ සිටඩෙල් Expedia ෆැබ් ෆැක්ට්සෙට් IBM ආයතනය SAP විද්‍යාගාර
අරා හැෂ් සෙවීම්

“ලබා දී ඇති අනුක්‍රමයක නොපවතින අනුක්‍රමය වැඩි කිරීමේ මූලද්‍රව්‍යය k-th අස්ථානගත වී ඇත” යන ගැටළුවෙහි දැක්වෙන්නේ ඔබට අරා දෙකක් ලබා දී ඇති බවයි. ඒවායින් එකක් ආරෝහණ අනුපිළිවෙලට සකස් කර ඇති අතර තවත් සාමාන්‍ය වර්ගීකරණ අංකයක් k සමඟ ඇත. සාමාන්‍ය අනුක්‍රමයෙහි නොපවතින නමුත් අනුපිළිවෙල අනුපිළිවෙල වැඩි කිරීමේදී kth අස්ථානගත වූ මූලද්‍රව්‍යය සොයා ගන්න.

උදාහරණයක්

දී ඇති අනුක්‍රමයක නොපවතින අනුක්‍රමය වැඩි කිරීමේ k-th මූලද්‍රව්‍යය

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

පැහැදිලි කිරීම

දී ඇති අරාවෙහි නොමැති වැඩි වන අනුක්‍රමයේ සංඛ්‍යා 0,8,14 වේ.

කේth අස්ථානගත වූ අංකය, 2nd අංකය 8 කි

දී ඇති අනුක්‍රමයක නොමැති අනුක්‍රමය වැඩි කිරීමේදී k-th අස්ථානගත වූ මූලද්‍රව්‍යය සොයා ගැනීමට ඇල්ගොරිතම

  1. හැෂ්සෙට්.
  2. දෙවන අරාවේ සියලුම අංග හැෂ්සෙට් තුළට දමන්න.
  3. කට්ටලයක් අස්ථානගතව ඇති මුදල 0 දක්වා.
  4. වැඩිවන අනුක්‍රමික අරාව හරහා ගමන් කරන අතරතුර, පරීක්ෂා කරන්න:
    1. කට්ටලයක අනුක්‍රමික අරා මූලද්‍රව්‍ය කිසිවක් අඩංගු නොවේ නම්
      1. අස්ථානගතවූ අගය 1 කින් වැඩි කරන්න.
      2. අස්ථානගත වූ අගය k ට සමාන දැයි පරීක්ෂා කරන්න.
        • සත්‍ය නම්, එම අරාව ආපසු දෙන්න [i].
  5. ලූපයෙන් පිටත -1 ආපසු යන්න.

පැහැදිලි කිරීම

ඔබට අරා දෙකක් සහ k අංකයක් ලබා දී ඇත. අරා දෙකෙන් එකක් වැඩි වන අනුක්‍රමයක් වන අතර අනෙක සාමාන්‍ය වර්ගීකරණය නොකළ අනුක්‍රමයකි. ගැටළු ප්‍රකාශයේ සඳහන් වන්නේ වර්ගීකරණය නොකළ අනුපිළිවෙලෙහි kth අස්ථානගත වූ මූලද්‍රව්‍යය සොයාගත යුතු බවයි.

අපි මේ සඳහා කට්ටලයක් භාවිතා කරන්නෙමු. අපි දෙවන අරාව හරහා ගමන් කරන්නෙමු බී[] එහි සියලු අගයන් කට්ටලයට ඇතුළු කරන්න. මෙයට හේතුව අපට එය පසුව පරීක්ෂා කර පළමු කට්ටලය සමඟ කට්ටලය සංසන්දනය කළ හැකි බැවිනි ඒ[]. අරාව []] හරහා ගමන් කරන විට, කට්ටලයේ අරාවේ නිශ්චිත අගය [i] අඩංගු නොවේ නම්. අපි වටිනාකම වැඩි කරමු අස්ථානගතව ඇති මුදල 1 කින් සහ අතුරුදහන් වූ ගණනය ලබා දී ඇති අංකයට සමාන දැයි එකවර පරීක්ෂා කරන්න. එය එසේ වුවහොත්, අපට පළමු අරාවේ මූලද්‍රව්‍යය නැවත ලබා දිය හැකිය.

අපි උදාහරණයක් සලකා බලමු.

උදාහරණයක්

array 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

කට්ටලය තුළ එය අඩංගු නොවන බැවින් එය අස්ථානගත වීම වැඩි වනු ඇතCount = missingCount + 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] එනම් 'XNUMX',

ප්‍රතිදානය 8 බවට පත්වේ.

කේතය

දී ඇති අනුක්‍රමයක නොපවතින අනුක්‍රමය වැඩි කිරීමේදී k-th අස්ථානගත වූ මූලද්‍රව්‍යය සොයා ගැනීමට 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

දී ඇති අනුක්‍රමයක නොපවතින අනුක්‍රමය වැඩි කිරීමේදී 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” අරාව 1 සහ අරාව 2 හි දිග වේ. අපි අරා දෙකේම සියලුම මූලද්රව්ය හරහා ගමන් කර ඇති බැවින්. කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (n2) එහිදී “N2” අරාව 2 හි දිග වේ. අපි දෙවන අරාවේ මූලද්‍රව්‍ය පමණක් හැෂ්සෙට් තුළ ගබඩා කර ඇති නිසා අවශ්‍ය අවකාශය රේඛීය වේ.