Ктх - решење за недостатак позитивног броја са кодом


Ниво тешкоће Лако
Често питани у фацебоок мицрософт
Ред Хасхинг

Изјава о проблему

У проблему „Ктх Миссинг Поситиве Нумбер“ добијамо низ арр, који је сортиран строго се повећава ред и број к.

Наш задатак је да откријемо Ктх позитиван број који недостаје у низу.

Пример

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

objašnjenje:

Ктх - решење за недостатак позитивног броја са кодом

Као и у датом низу, први број који недостаје је 5, а други број који недостаје 6. Дакле, одговор је 6.

Бруте Форце А.ппроацх за Ктх решење за недостатак позитивног броја са кодом

Приступ грубе силе за решавање овог проблема је следећи:

  1. Пређите низ.
  2. Сваки пут ћемо израчунати број бројева који недостају.
  3. ако је број недостајућих позитивних бројева већи или једнак к онда ћемо вратити и + к.
  4. Након комплетног преласка низа ако је број елемената који недостају мањи од к, вратићемо величину низа + к.

Имплементација

Ц ++ код за Ктх који недостаје позитиван број

#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

Јава код за Ктх који недостаје позитиван број

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

Анализа сложености Ктх решења са Леетцоде недостајућим позитивним бројем

Временска сложеност

Временска сложеност горњег кода је Он) јер користимо линеарну претрагу којој је у најгорем случају потребно О (н) време. Овде је н дужина датог низа.

Свемирска сложеност

Сложеност простора горњег кода је О (1) јер користимо само променљиву за чување одговора.

Бинарна претрага А.ппроацх за Ктх решење за недостатак позитивног броја са кодом

Временска сложеност горњег алгоритма је О (н), јер ћемо у најгорем случају можда морати да пређемо цео низ. Временску сложеност решења можемо побољшати помоћу бинарне претраге уместо линеарне претраге.

  1. прво дефинишимо опсег наше претраге за бинарну претрагу. Дакле, почетак ће бити индекс 0, а крај ће бити последњи индекс датог низа.
  2. Пронаћи ћемо средњи индекс, а затим ћемо проверити да ли је број недостајућих позитивних бројева мањи од к:
    1. тада ће старт постати средина + 1.
    2. иначе ће крај постати средина.
  3. повратни крај + к.

Имплементација

Ц ++ код за Ктх који недостаје позитиван број

#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

Јава код за Ктх који недостаје позитиван број

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

Анализа сложености Ктх решења са Леетцоде недостајућим позитивним бројем

Временска сложеност

Временска сложеност горњег кода је О (лог н) јер користимо бинарну претрагу којој је у најгорем случају потребно О (логн) време. Овде је н дужина датог низа.

Свемирска сложеност

Сложеност простора горњег кода је О (1) јер користимо само променљиву за чување одговора.

Референце