Press "Enter" to skip to content

Posts tagged as “bucket”

花花酱 LeetCode 164. Maximum Gap

https://leetcode.com/problems/maximum-gap/description/

Problem:

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

题目大意:

给你一个没有排序的正整数数组。输出排序后,相邻元素的差的最大值(Max Gap)。需要在线性时间内解决。

Example:

Input:  [5, 0, 4, 2, 12, 10]

Output: 5

Explanation: 

Sorted: [0, 2, 4, 5, 10, 12]

max gap is 10 – 5 = 5

Idea:

Bucket sort. Use n buckets to store all the numbers. For each bucket, only track the min / max value.

桶排序。用n个桶来存放数字。对于每个桶,只跟踪存储最大值和最小值。

max gap must come from two “adjacent” buckets, b[i], b[j], j > i, b[i+1] … b[j – 1] must be empty.

max gap 只可能来自”相邻”的两个桶 b[i] 和 b[j], j > i, b[i] 和 b[j] 之间的桶(如果有)必须为空。

max gap = b[j].min – b[i].min

Time complexity: O(n)

时间复杂度: O(n)

Space complexity: O(n)

空间复杂度: O(n)

Solution:

C++

 

花花酱 LeetCode 719. Find K-th Smallest Pair Distance

题目大意:给你一个数组,返回所有数对中,绝对值差第k小的值。

Problem:

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1:

Note:

  1. 2 <= len(nums) <= 10000.
  2. 0 <= nums[i] < 1000000.
  3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

Idea

Bucket sort

Binary search / dp

Solution

C++ / binary search

 

C++ / bucket sort w/ vector O(n^2)

Related Problems:

花花酱 LeetCode 683. K Empty Slots

题目大意:有n个花盆,第i天,第flowers[i]个花盆的花会开。问是否存在一天,两朵花之间有k个空花盆。

Problem:

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn’t such day, output -1.

Example 1:

Input: 
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.

Example 2:

Input: 
flowers: [1,2,3]
k: 1
Output: -1

Note:

  1. The given array will be in the range [1, 20000].

Idea:

BST/Buckets



 

Solution 2: BST

C++

Solution 3: Buckets

C++

Solution 1: TLE with latest test cases

C++

Java

Python