1539. Kth Missing Positive Number

LeetCode easy оригинал: C# #array #backtracking #csharp #easy #leetcode #search #sort
LeetCode Static

Дан массив

arr

из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число

k

.

Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.

Пример:

Input: arr = [2,3,4,7,11], k = 5

Output: 9

Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

C# решение

сопоставлено/оригинал 
public class Solution {
    public int FindKthPositive(int[] arr, int k) {
        if (k <= arr[0] - 1) {
            return k;
        }
        k -= arr[0] - 1;
        int n = arr.Length;
        for (int i = 0; i < n - 1; ++i) {
            int currMissing = arr[i + 1] - arr[i] - 1;
            if (k <= currMissing) {
                return arr[i] + k;
            }
            k -= currMissing;
        }
        return arr[n - 1] + k;
    }
}

C++ решение

auto-draft, проверить перед отправкой 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindKthPositive(vector<int>& arr, int k) {
        if (k <= arr[0] - 1) {
            return k;
        }
        k -= arr[0] - 1;
        int n = arr.size();
        for (int i = 0; i < n - 1; ++i) {
            int currMissing = arr[i + 1] - arr[i] - 1;
            if (k <= currMissing) {
                return arr[i] + k;
            }
            k -= currMissing;
        }
        return arr[n - 1] + k;
    }
}

Java решение

сопоставлено/оригинал 
class Solution {
    public int findKthPositive(int[] arr, int k) {
        if (k <= arr[0] - 1) {
            return k;
        }
        k -= arr[0] - 1;
        int n = arr.length;
        for (int i = 0; i < n - 1; ++i) {
            int currMissing = arr[i + 1] - arr[i] - 1;
            if (k <= currMissing) {
                return arr[i] + k;
            }
            k -= currMissing;
        }
        return arr[n - 1] + k;
    }
}

JavaScript решение

сопоставлено/оригинал 
class Solution {
    findKthPositive(arr, k) {
        if (k <= arr[0] - 1) {
            return k;
        }
        k -= arr[0] - 1;
        const n = arr.length;
        for (let i = 0; i < n - 1; i++) {
            const currMissing = arr[i + 1] - arr[i] - 1;
            if (k <= currMissing) {
                return arr[i] + k;
            }
            k -= currMissing;
        }
        return arr[n - 1] + k;
    }
}

Go решение

сопоставлено/оригинал 
func findKthPositive(arr []int, k int) int {
    if k <= arr[0] - 1 {
        return k
    }
    k -= arr[0] - 1
    n := len(arr)
    for i := 0; i < n - 1; i++ {
        currMissing := arr[i + 1] - arr[i] - 1
        if k <= currMissing {
            return arr[i] + k
        }
        k -= currMissing
    }
    return arr[n - 1] + k
}

Algorithm

Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.

Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.

Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии
Активных вакансий пока нет.