k- րդ պակասող տարրը հաջորդականության ավելացման մեջ, որը առկա չէ տվյալ հաջորդականության մեջ  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Միջնաբերդ Expedia Ֆաբ Փաստեր IBM SAP լաբորատորիաներ
Դասավորություն Խանգարել Որոնում

«Հաջորդականության ավելացման k- րդ տարրը, որը չկա տվյալ հաջորդականության մեջ» խնդիրը նշում է, որ ձեզ տրվում է երկու զանգված: Դրանցից մեկը դասավորված է աճման կարգով, և մեկ այլ նորմալ չսորտավորված զանգված `k թվով: Գտեք kth բացակայող տարրը, որը ներկա չէ նորմալ հաջորդականությամբ, բայց առկա է կարգի հաջորդականության զանգվածի մեծացման մեջ:

Օրինակ  

k- րդ պակասող տարրը հաջորդականության ավելացման մեջ, որը առկա չէ տվյալ հաջորդականության մեջPin

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

բացատրություն

Աճող հաջորդականության թվերը, որոնք առկա չեն տվյալ զանգվածում, 0,8,14 են:

Կth բացակայող թիվ, այսինքն ՝ 2nd համարը 8 է

Ալգորիթմ `հաջորդականության ավելացման մեջ k- րդ պակասող տարր գտնելու համար, որը տվյալ հաջորդականության մեջ չկա  

  1. Հայտարարել ա HashSet.
  2. Երկրորդ զանգվածի բոլոր տարրերը դրեք HashSet- ի մեջ:
  3. հավաքածու բացակայում է Ինչպես 0:
  4. Մինչ ավելացող հաջորդական զանգվածն անցնելիս ստուգեք ՝
    1. Եթե ​​բազմությունը չի պարունակում զանգվածի հաջորդականության որևէ տարր
      1. Բարձրացրե՛ք բաց թողած հաշվարկի արժեքը 1-ով:
      2. Ստուգեք, թե արդյոք բացակայում է հաշվարկի արժեքը հավասար է k- ի:
        • Եթե ​​ճիշտ է, վերադարձիր այդ զանգվածը [i]:
  5. Օղակից դուրս եկեք -1:

բացատրություն

Ձեզ տրվում է երկու զանգված և k թիվ: Երկու զանգվածներից մեկը աճող հաջորդականություն է, իսկ մյուսը `նորմալ չհավաքված հաջորդականություն: Խնդրի հայտարարությունն ասում է, որ տեսակավորված հաջորդականության զանգվածում պետք է գտնել kth բացակայող տարրը, որը չկան տեսակավորված զանգվածում:

Տես նաեւ,
Rayանգվածում գտեք ամենամեծ d- ն այնպես, որ a + b + c = d

Դրա համար մենք պատրաստվում ենք օգտագործել հավաքածու: Մենք պատրաստվում ենք անցնել երկրորդ զանգվածը բ [] և իր ամբողջ արժեքը ներդիր հավաքածուի մեջ: Սա այն պատճառով է, որ մենք կարող ենք ավելի ուշ ստուգել այն և համեմատել հավաքածուն առաջին զանգվածի հետ ա [], A [] զանգվածն անցնելիս, եթե բազմությունը չի պարունակում 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}

Մենք պետք է անցնենք a [] զանգվածի տարրերը և ստուգենք, եթե հավաքածուն չի պարունակում arr [i] տարր,

i = 0, arr [i] = 0

Հավաքածուն այն չի պարունակում, ուստի այն կավելացնի missingCount = բացակայում էՀաշիվը + 1

missingCount = 1, ստուգեք ՝ արդյոք MissCount == 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, ուստի այն կավելացնի missingCount = დაკარგულიՀաշիվ + 1

missingCount = 2, ստուգեք ՝ արդյոք დაკარგულიCount == k, դա ճիշտ է, այնպես որ այն կվերադարձնի ar [i] - ը, որը «8» է

Արդյունքը կդառնա 8:

Տես նաեւ,
Մշտական ​​ժամանակային տիրույթն ավելացնում է գործողությունը զանգվածի վրա

Կոդ  

C ++ կոդ `հաջորդականության ավելացման մեջ 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

Java կոդ `հաջորդականության ավելացման մեջ 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

Բարդության վերլուծություն  

Timeամանակի բարդություն

O (n1 + n2) որտեղ «N1» և «N2» զանգվածի 1 և զանգվածի 2 երկարությունն են: Քանի որ մենք անցել ենք բոլոր զանգվածներից և՛ բոլոր զանգվածներից: Timeամանակի բարդությունը գծային է:

Տիեզերական բարդություն

O (n2) որտեղ «N2» զանգվածի երկարությունն է 2: Քանի որ HashSet- ում մենք պահպանել ենք միայն երկրորդ զանգվածի տարրերը, պահանջվող տարածքը նույնպես գծային է: