5 篇博文含有标签「桶排序」

LCR 060.前 K 个高频元素

2022年1月19日 · 阅读需 3 分钟

1、题干

给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 10⁵
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

注意：本题与主站 347 题相同：https://leetcode-cn.com/problems/top-k-frequent-elements/

2、解法1-API排序

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入数组并使用排序API按数量降序排序，最后返回前 k 个数字

3、代码

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const arr = [];
    for (const kv of map) arr.push(kv);
    return arr.sort((a, b) => b[1] - a[1]).slice(0, k).map(a => a[0]);
};

4、复杂度

时间复杂度： $O(nlogn)$
空间复杂度： $O(n)$

5、解法2-桶排序

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入按数量存入桶中，最后返回前 k 个数字。其时间复杂度为 $O(n)$ ，解决了进阶问题。

6、代码

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const buckets = new Array(nums.length + 1);
    for (const [n, v] of map) !buckets[v] ? buckets[v] = [n] : buckets[v].push(n);

    const res = [];
    for (let i = buckets.length - 1; i > -1; i--) {
        if (res.length >= k) break;
        if (buckets[i]) res.push(...buckets[i]);
    }

    return res.length > k ? res.slice(0, k) : res;
};

7、复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

剑指 Offer II 060.出现频率最高的 k 个数字

2022年1月19日 · 阅读需 3 分钟

Whilconn

1、题干

给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 10⁵
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

注意：本题与主站 347 题相同：https://leetcode-cn.com/problems/top-k-frequent-elements/

2、解法1-API排序

先使用哈希映射 map 对所有整数进行计数，然后将 map 中的键值对存入数组并使用排序API按数量降序排序，最后返回前 k 个数字

3、代码

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const arr = [];
    for (const kv of map) arr.push(kv);
    return arr.sort((a, b) => b[1] - a[1]).slice(0, k).map(a => a[0]);
};

4、复杂度

时间复杂度： $O(nlogn)$
空间复杂度： $O(n)$

5、解法2-桶排序

6、代码

var topKFrequent = function (nums, k) {
    const map = new Map();
    for (const n of nums) map.set(n, 1 + (map.get(n) || 0));

    const buckets = new Array(nums.length + 1);
    for (const [n, v] of map) !buckets[v] ? buckets[v] = [n] : buckets[v].push(n);

    const res = [];
    for (let i = buckets.length - 1; i > -1; i--) {
        if (res.length >= k) break;
        if (buckets[i]) res.push(...buckets[i]);
    }

    return res.length > k ? res.slice(0, k) : res;
};

7、复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

LCR 057.存在重复元素 III

2022年1月13日 · 阅读需 3 分钟

Whilconn

1、题干

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

提示：

0 <= nums.length <= 2 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁴
0 <= t <= 2³¹ - 1

注意：本题与主站 220 题相同： https://leetcode-cn.com/problems/contains-duplicate-iii/

2、解法1-暴力解法

双层遍历，外层从头到尾遍历，内层遍历外层元素之后的 k 个元素，如果找到两个元素差值的绝对值小于等于 t 则结果为 true。

注意：内层只需要遍历后 k 个元素，因为前 k 个元素在外层遍历时已经判断过

3、复杂度

时间复杂度： $O(nk)$
空间复杂度： $O(1)$

4、代码

var containsNearbyAlmostDuplicate = function (nums, k, t) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j <= i + k && j < nums.length; j++) {
            if (Math.abs(nums[j] - nums[i]) <= t) return true;
        }
    }
    return false;
};

5、执行结果

执行用时: 500 ms 内存消耗: 39.1 MB

6、解法2-桶排序

遍历过程中使用桶排序维护 k 个元素的有序集合，桶的大小设置为 t + 1 以保证同一个桶内出现两个元素 n1 和 n2 时，必定有 abs(n1 - n2) <= t 即结果为true，另外如果相邻的桶内有数字且满足与当前数字的差值的绝对值小于等于 t 则结果为 true。

7、复杂度

时间复杂度： $O(n)$
空间复杂度： $O(k)$

8、代码

var containsNearbyAlmostDuplicate = function (nums, k, t) {
    const buckets = new Map();
    const genIdx = (n) => ((n + 2147483648) / (t + 1)) >> 0;

    for (let i = 0; i < nums.length; i++) {
        if (i > k) buckets.delete(genIdx(nums[i - k - 1]));
        const idx = genIdx(nums[i]);
        if (buckets.has(idx)) return true;
        if (buckets.has(idx - 1) && nums[i] - buckets.get(idx - 1) <= t) return true;
        if (buckets.has(idx + 1) && buckets.get(idx + 1) - nums[i] <= t) return true;
        buckets.set(idx, nums[i]);
    }

    return false;
};

9、执行结果

剑指 Offer II 057.值和下标之差都在给定的范围内

2022年1月13日 · 阅读需 3 分钟

Whilconn

1、题干

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

提示：

0 <= nums.length <= 2 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁴
0 <= t <= 2³¹ - 1

注意：本题与主站 220 题相同： https://leetcode-cn.com/problems/contains-duplicate-iii/

2、解法1-暴力解法

双层遍历，外层从头到尾遍历，内层遍历外层元素之后的 k 个元素，如果找到两个元素差值的绝对值小于等于 t 则结果为 true。

注意：内层只需要遍历后 k 个元素，因为前 k 个元素在外层遍历时已经判断过

3、复杂度

时间复杂度： $O(nk)$
空间复杂度： $O(1)$

4、代码

var containsNearbyAlmostDuplicate = function (nums, k, t) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j <= i + k && j < nums.length; j++) {
            if (Math.abs(nums[j] - nums[i]) <= t) return true;
        }
    }
    return false;
};

5、执行结果

执行用时: 500 ms 内存消耗: 39.1 MB

6、解法2-桶排序

7、复杂度

时间复杂度： $O(n)$
空间复杂度： $O(k)$

8、代码

var containsNearbyAlmostDuplicate = function (nums, k, t) {
    const buckets = new Map();
    const genIdx = (n) => ((n + 2147483648) / (t + 1)) >> 0;

    for (let i = 0; i < nums.length; i++) {
        if (i > k) buckets.delete(genIdx(nums[i - k - 1]));
        const idx = genIdx(nums[i]);
        if (buckets.has(idx)) return true;
        if (buckets.has(idx - 1) && nums[i] - buckets.get(idx - 1) <= t) return true;
        if (buckets.has(idx + 1) && buckets.get(idx + 1) - nums[i] <= t) return true;
        buckets.set(idx, nums[i]);
    }

    return false;
};

9、执行结果

347.前 K 个高频元素

2021年11月6日 · 阅读需 2 分钟

Whilconn

1、题干

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 10⁵
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

解题思路

创建哈希映射map，用于统计数字出现次数，key为数字，value为出现次数
创建数组arr，用于统计每个出现次数对应的数字集合，数组下标代表数字出现次数，值为出现次数与之相等的数字的集合
倒序遍历数组arr，提取前出现频率前 k 高的数字

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const map = {};
    for (let i = 0; i < nums.length; i++) {
        map[nums[i]] = (map[nums[i]] || 0) + 1;
    }

    const matrix = Object.entries(map);
    const arr = [];
    for (let i = 0; i < matrix.length; i++) {
        const [n, c] = matrix[i];
        if (!arr[c]) arr[c] = [];
        arr[c].push(+n);
    }

    const res = [];
    for (let i = arr.length - 1; i > -1; i--) {
        if (arr[i] && res.length < k) {
            res.push(...arr[i].slice(0, k - res.length));
        }
    }

    return res;
};

1、题干​

2、解法1-API排序​

3、代码​

4、复杂度​

5、解法2-桶排序​

6、代码​

7、复杂度​

1、题干​

2、解法1-API排序​

3、代码​

4、复杂度​

5、解法2-桶排序​

6、代码​

7、复杂度​

1、题干​

2、解法1-暴力解法​

3、复杂度​

4、代码​

5、执行结果​

6、解法2-桶排序​

7、复杂度​

8、代码​

9、执行结果​

1、题干​

2、解法1-暴力解法​

3、复杂度​

4、代码​

5、执行结果​

6、解法2-桶排序​

7、复杂度​

8、代码​

9、执行结果​

1、题干​

解题思路​

代码​

1、题干

2、解法1-API排序

3、代码

4、复杂度

5、解法2-桶排序

6、代码

7、复杂度

1、题干

2、解法1-API排序

3、代码

4、复杂度

5、解法2-桶排序

6、代码

7、复杂度

1、题干

2、解法1-暴力解法

3、复杂度

4、代码

5、执行结果

6、解法2-桶排序

7、复杂度

8、代码

9、执行结果

1、题干

2、解法1-暴力解法

3、复杂度

4、代码

5、执行结果

6、解法2-桶排序

7、复杂度

8、代码

9、执行结果

1、题干

解题思路

代码