K-е решение Leetcode с отсутствующим положительным числом


Сложный уровень Легко
Часто спрашивают в Facebook Microsoft
массив хеширования

Постановка задачи

В задаче «K-е пропущенное положительное число» нам дан массив arr, который сортируется в строго увеличивается порядок и номер k.

Наша задача - найти K-е положительное пропущенное число в массиве.

Пример

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

Объяснение:

K-е решение Leetcode с отсутствующим положительным числом

Как и в данном массиве, первое пропущенное число - 5, второе - 6. Итак, ответ - 6.

Грубая сила Approach для решения Leetcode для пропущенного положительного числа K

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

  1. Пройдите по массиву.
  2. Каждый раз мы будем подсчитывать количество пропущенных чисел.
  3. если количество пропущенных положительных чисел больше или равно k, мы вернем i + k.
  4. После полного обхода массива, если количество пропущенных элементов меньше k, мы вернем размер массива + k.

Реализация

Код C ++ для пропущенного положительного числа K

#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 для пропущенного положительного числа K

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

Анализ сложности K-го решения Leetcode с отсутствующим положительным числом

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

Временная сложность приведенного выше кода О (п) потому что мы используем линейный поиск, который в худшем случае занимает O (n) времени. Здесь n - длина данного массива.

Пространство сложности

Пространственная сложность приведенного выше кода равна O (1) потому что мы используем только переменную для хранения ответа.

Двоичный поиск Approach для решения Leetcode для пропущенного положительного числа K

Временная сложность вышеупомянутого алгоритма составляет O (n), потому что в худшем случае нам может потребоваться пройти через весь массив. Мы можем улучшить временную сложность решения, используя двоичный поиск вместо линейного поиска.

  1. давайте сначала определим диапазон нашего поиска для двоичного поиска. Таким образом, начало будет индексом 0, а конец будет последним индексом данного массива.
  2. Мы найдем средний индекс, затем проверим, меньше ли количество пропущенных положительных чисел k:
    1. тогда start станет mid + 1.
    2. иначе конец станет серединой.
  3. вернуть конец + k.

Реализация

Код C ++ для пропущенного положительного числа K

#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 для пропущенного положительного числа K

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

Анализ сложности K-го решения Leetcode с отсутствующим положительным числом

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

Временная сложность приведенного выше кода O (журнал n) потому что мы используем двоичный поиск, который в худшем случае занимает время O (logn). Здесь n - длина данного массива.

Пространство сложности

Пространственная сложность приведенного выше кода равна O (1) потому что мы используем только переменную для хранения ответа.

дело