Kth Адсутнічае станоўчы нумар рашэння Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў facebook Microsoft
масіў хэшавання

Пастаноўка праблемы

У задачы «Kth адсутнічае станоўчы нумар» мы атрымліваем масіў arr, які адсартаваны строга расце парадак і лік k.

Наша задача - высветліць Kth дадатнага нумара ў масіве.

Прыклад

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

Тлумачэнне:

Kth Адсутнічае станоўчы нумар рашэння Leetcode

Як і ў дадзеным масіве, першы адсутнічае лік роўны 5, а другі адсутнічае лік 6. Такім чынам, адказ 6.

Грубая сіла А.pproach для Kth Адсутнічае станоўчы нумар Рашэнне Leetcode

Падыход грубай сілы да вырашэння гэтай праблемы заключаецца ў наступным:

  1. Прайсці масіў.
  2. Кожны раз мы будзем вылічваць колькасць прапушчаных лікаў.
  3. калі колькасць прапушчаных дадатных лікаў больш або роўна k, мы вернем i + k.
  4. Пасля поўнага абходу масіва, калі колькасць адсутных элементаў менш за 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

Аналіз складанасці рашэння Ket з пропушчаным дадатным лікам

Часовая складанасць

Часавая складанасць вышэйзгаданага кода Аб (п) таму што мы выкарыстоўваем лінейны пошук, які займае O (n) час у горшым выпадку. Тут n - даўжыня дадзенага масіва.

Касмічная складанасць

Касмічная складанасць вышэйзгаданага кода складаецца ў O (1) таму што мы выкарыстоўваем толькі зменную для захоўвання адказу.

Двайковы пошук Approach для Kth Адсутнічае станоўчы нумар Рашэнне Leetcode

Часавая складанасць вышэйапісанага алгарытму складае 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

Аналіз складанасці рашэння Ket з пропушчаным дадатным лікам

Часовая складанасць

Часавая складанасць вышэйзгаданага кода O (часопіс n) таму што мы выкарыстоўваем двайковы пошук, які займае час O (logn) у горшым выпадку. Тут n - даўжыня дадзенага масіва.

Касмічная складанасць

Касмічная складанасць вышэйзгаданага кода складаецца ў O (1) таму што мы выкарыстоўваем толькі зменную для захоўвання адказу.

Спасылкі