Решение: максимальный разрыв

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашел его полезным, Пожалуйста, как этот пост и/или УПОТАТЬ Мое решение пост на форумах LeetCode Отказ

Проблема лецкода # 164 (HARD): Максимальный пробел

Описание:

( Перейти к : Идея решения Код : JavaScript | Python |. Java |. C ++

Учитывая целочисленный массив Nums , вернуть Максимальная разница между двумя последовательными элементами в его сортировке Отказ Если массив содержит менее двух элементов, return 0 Отказ

Вы должны написать алгоритм, который работает в линейном времени и использует линейное дополнительное пространство.

Примеры:

Ограничения:

• 1. Длина ^ 4.
• 0 [я] ^ 9

Идея:

( Перейти к : Описание проблемы Код : JavaScript | Python |. Java |. C ++

Для этой проблемы нам не нужно на самом деле отсортировать каждый элемент, который займет больше времени, чем Вовремя . Что нам нужно сделать, это найти способ объединить числа вместе таким образом, чтобы позволить нам проверить большие зазоры между последовательными числами. Для этого мы можем обратиться к Ведро сортирует Отказ

Сортировка ведра включает в себя создание массива ( ведра ), в которых элементы представляют собой ведра, которые охватывают распространение чисел, которые будут отсортированы. Представьте себе, пытаясь сортировать колоду карт; Это займет только один раз через колоду, чтобы полностью разобраться в 13 «Ведра», один для каждого значения. Тогда мы могли бы пройти через отдельные ведра и выполнять другой, меньший сортировку, прежде чем присоединиться к всей палубе вместе.

В этой ситуации, однако, нам нужно только выполнить первую часть сортировки ведра. Идея состоит в том, чтобы определить размер наших ведер, так что максимальный разрыв обязательно будет больше одного ведра. Это означало бы, что наш ответ может быть найден, сравнивая наибольшее значение в каждом ведре с самым низким значением в следующем занятом ведре.

Для достижения правильного размера ведра ( Bsize ) для этого работать, нам нужно будет повторять Nums Один раз, чтобы найти общий диапазон ( Hi – Lo ), затем используйте, что выяснить абсолютное наименьшее возможное максимальное значение пробела ( (HI – LO)/(NUM. Length – 1) ). Если мы обязательно определим размер ведра меньший Чем это значение, то, как говорилось ранее, два числа, которые образуют максимальный зазор, должны быть найдены в отдельных ведрах.

Так как именно есть N Номера распространяются по всему ведрам, и поскольку он требует только одной итерации каждого числа в ведре, чтобы наблюдать за локальными значениями высокого и LO ( Curhi, Curlo ), то он займет всего O (n) время Чтобы выполнить этот процесс для всего Ведра множество. И поскольку нам нужно только сделать одно сравнение на пару ведер с последовательными числами, и, поскольку есть только максимум 2 * n Ведра, сравнения примут только O (n) время , также.

Нам просто нужно будет помнить, что мы помним высокое значение предыдущего оккупированного ведра ( Prevhi ) для следующего сравнения, а также отслеживание наилучшего результата, обнаруженного до сих пор ( ANS ). Затем, как только мы достигнем конца нашего Ведра Массив, мы можем просто Вернуть АНС Отказ

• Сложность времени: O (n) куда N это длина числа
  • находка Привет а также воплощение в числа : НА)
  • наполнять ведра : НА)
  • найти все ведро Привет ‘песок воплощение : НА)
  • Сравнение всех пробелов в ведре: НА) до 2 * N. ведра
• Космическая сложность: O (n) для N Числа распространяются среди наиболее 2 * N. ведра

Код JavaScript:

( Перейти к : Описание проблемы Идея решения

var maximumGap = function(nums) {
    if (nums.length < 2) return 0
    let hi = 0, lo = 2e9, ans = 0
    for (let n of nums)
        hi = Math.max(hi, n), lo = Math.min(lo, n)
    let bsize = ~~((hi - lo) / (nums.length - 1)) || 1,
        buckets = Array.from({length: ~~((hi - lo) / bsize) + 1}, () => [])
    for (let n of nums)
        buckets[~~((n - lo) / bsize)].push(n)
    let currhi = 0
    for (let b of buckets) {
        if (!b.length) continue
        let prevhi = currhi || b[0], currlo = b[0]
        for (let n of b) 
            currhi = Math.max(currhi, n), currlo = Math.min(currlo, n)
        ans = Math.max(ans, currlo - prevhi)
    }
    return ans
};

Код Python:

( Перейти к : Описание проблемы Идея решения

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2: return 0
        hi, lo, ans = max(nums), min(nums), 0
        bsize = (hi - lo) // (len(nums) - 1) or 1
        buckets = [[] for _ in range(((hi - lo) // bsize) + 1)]
        for n in nums:
            buckets[(n - lo) // bsize].append(n)
        currhi = 0
        for b in buckets:
            if not len(b): continue
            prevhi, currlo = currhi or b[0], b[0]
            for n in b: 
                currhi, currlo = max(currhi, n), min(currlo, n)
            ans = max(ans, currlo - prevhi)
        return ans

Java код:

( Перейти к : Описание проблемы Идея решения

class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;
        int hi = 0, lo = Integer.MAX_VALUE, ans = 0;
        for (int n : nums) {
            hi = Math.max(hi, n);
            lo = Math.min(lo, n);
        }
        int bsize = Math.max((hi - lo) / (nums.length - 1), 1);
        List> buckets = new ArrayList<>();
        for (int i = (hi - lo) / bsize; i >= 0; i--)
            buckets.add(new ArrayList<>());
        for (int n : nums)
            buckets.get((n - lo) / bsize).add(n);
        int currhi = 0;
        for (List b : buckets) {
            if (b.isEmpty()) continue;
            int prevhi = currhi > 0 ? currhi : b.get(0), currlo = b.get(0);
            for (int n : b) {
                currhi = Math.max(currhi, n);
                currlo = Math.min(currlo, n);
            }
            ans = Math.max(ans, currlo - prevhi);
        }
        return ans;
    }
}

C ++ код:

( Перейти к : Описание проблемы Идея решения

class Solution {
public:
    int maximumGap(vector& nums) {
        if (nums.size() < 2) return 0;
        int hi = 0, lo = INT_MAX, ans = 0;
        for (auto& n : nums)
            hi = max(hi, n), lo = min(lo, n);
        int bsize = max(int((hi - lo) / (nums.size() - 1)), 1);
        vector> buckets((hi - lo) / bsize + 1, vector());
        for (auto& n : nums)
            buckets[(n - lo) / bsize].push_back(n);
        int currhi = 0;
        for (auto& b : buckets) {
            if (b.empty()) continue;
            int prevhi = currhi ? currhi : b[0], currlo = b[0];
            for (auto& n : b)
                currhi = max(currhi, n), currlo = min(currlo, n);
            ans = max(ans, currlo - prevhi);
        }
        return ans;
    }
};

Оригинал: “https://dev.to/seanpgallivan/solution-maximum-gap-212k”