Kth Դրական համարի բաց թողնված կոդերի լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են facebook Microsoft
Դասավորություն Հեշինգ

Խնդրի հայտարարություն

«Kth Դրական համարը բացակայող» խնդրում մեզ տրվում է զանգվածի arr, որը տեսակավորվում է խստորեն աճող կարգը և թիվը k.

Մեր խնդիրն է պարզել զանգվածում Kth- ի դրական պակասող թիվը:

Օրինակ

arr = [1,2,3,4], k = 2
6

Բացատրությունը.

Kth Դրական համարի բաց թողնված կոդերի լուծում

Ինչպես տրված զանգվածում, առաջին բացակայող թիվը 5 է, իսկ երկրորդ բացակայող թիվը ՝ 6. Այսպիսով, պատասխանը 6 է:

Brute Force Apthopach Kth Missing Positive Number Leetcode Solution

Այս խնդրի լուծման համար կոպիտ ուժի մոտեցումը հետևյալն է.

  1. Անցեք զանգվածը:
  2. Ամեն անգամ մենք հաշվարկելու ենք բացակայող թվերի քանակը:
  3. եթե բացակայող դրական թվերի քանակը մեծ է կամ հավասար է k- ին, մենք կվերադարձնենք i + k:
  4. Rayանգվածի ամբողջական անցումից հետո, եթե բացակայող տարրերի քանակը պակաս է k- ից, մենք կվերադարձնենք զանգվածի + k չափը:

Իրականացման

C ++ ծածկագիր Kth- ի համար դրական թվի բացակայության համար

#include <bits/stdc++.h> 
using namespace std; 
    int findKthPositive(vector<int>& arr, int k) {
        for(int i=0;i<arr.size();i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.size()+k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}
6

Java- ի կոդը Kth- ի համարը, որը բացակայում է

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] arr, int k) {
        for(int i=0;i<arr.length;i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.length+k;
    }   
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}
6

Kth- ի դրական համարի բաց թողնված կոդերի լուծույթի բարդության վերլուծություն

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

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n) քանի որ մենք օգտագործում ենք գծային որոնում, որը վատագույն դեպքում O (n) ժամանակ է խլում: Այստեղ n- ը տրված զանգվածի երկարությունն է:

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

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք պատասխանը պահելու համար օգտագործում ենք միայն փոփոխական:

Երկուական որոնում Աpthopach Kth Missing Positive Number Leetcode Solution

Վերոնշյալ ալգորիթմի ժամանակի բարդությունը O (n) է, քանի որ մեզ կարող է անհրաժեշտ լինել վատթարագույն դեպքում հատել ամբողջական զանգվածը: Մենք կարող ենք բարելավել լուծման ժամանակի բարդությունը ՝ գծային որոնման փոխարեն օգտագործելով երկուական որոնում:

  1. եկեք նախ սահմանենք երկուական որոնման համար մեր որոնման տիրույթը: Այսպիսով, մեկնարկը կլինի 0 ինդեքսը և վերջը կլինի տվյալ զանգվածի վերջին ինդեքսը:
  2. Մենք կգտնենք միջին ինդեքսը, այնուհետև կստուգենք, թե պակասող դրական թվերի թիվը պակաս է k- ից:
    1. ապա մեկնարկը կդառնա + 1-ի կես:
    2. հակառակ դեպքում վերջը կդառնա կես:
  3. վերադարձի ավարտ + k.

Իրականացման

C ++ ծածկագիր Kth- ի համար դրական թվի բացակայության համար

#include <bits/stdc++.h> 
using namespace std; 
int findKthPositive(vector<int>& A, int k) {
        int l = 0, r = A.size(), m;
        while (l < r) {
            m = (l + r) / 2;
            if (A[m] - 1 - m < k)
                l = m + 1;
            else
                r = m;
        }
        return l + k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}
6

Java- ի կոդը Kth- ի համարը, որը բացակայում է

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] A, int k) {
        int l = 0, r = A.length, m;
        while (l < r) {
            m = (l + r) / 2;
            if (A[m] - 1 - m < k)
                l = m + 1;
            else
                r = m;
        }
        return l + k;
    }  
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}
6

Kth- ի դրական համարի բաց թողնված կոդերի լուծույթի բարդության վերլուծություն

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

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (տեղեկամատյան n) քանի որ մենք օգտագործում ենք երկուական որոնում, որը վատագույն դեպքում O (logn) ժամանակ է խլում: Այստեղ n- ը տրված զանգվածի երկարությունն է:

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

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք պատասխանը պահելու համար օգտագործում ենք միայն փոփոխական:

Սայլակ