leetcode
leetcode 1851 ~ 1900
找到和最大的长度为 K 的子序列

找到和最大的长度为 K 的子序列

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.1 MB


/*
 * 思路:
 * 1. 创建一个存储索引和值的列表。
 * 2. 对列表按值进行排序(从大到小)。
 * 3. 取前k个最大的值及其索引。
 * 4. 根据索引对这些值排序以保持原数组的顺序。
 * 5. 返回结果。
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        return IntStream.range(0, nums.length)
                .mapToObj(i -> new int[]{nums[i], i})
                .sorted((a, b) -> b[0] - a[0])
                .limit(k)
                .sorted(Comparator.comparingInt(a -> a[1]))
                .mapToInt(a -> a[0])
                .toArray();
    }
}

解释

方法:

题解的思路主要是使用贪心算法来找到和最大的k个元素的子序列。首先对数组进行排序,然后取出最大的k个元素。这k个元素构成了和最大的子序列,但可能不保持原始顺序。为了保持原始顺序,我们使用一个哈希表记录这k个元素及其出现的次数。接着,我们遍历原始数组,按照原始顺序收集这些元素,直到收集完这k个元素。这样我们既保证了子序列的和最大,也保证了顺序。

时间复杂度:

O(n log n)

空间复杂度:

O(k)

代码细节讲解

🦆
在解法中采用排序后选择最大的k个元素的方法,这种做法在什么情况下可能不适用?
当数组非常大或者元素难以比较时,排序步骤可能非常耗时或者不可行。此外,如果内存限制很严格,排序可能需要额外的存储空间。在这些情况下,可以考虑使用其他方法,如使用最小堆(优先队列)维护当前最大的k个元素。
🦆
为什么选择使用哈希表来跟踪最大k个元素的出现次数?使用其他数据结构(如数组)会有什么效果?
哈希表可以快速地插入、检索和更新元素的出现次数,这对于此算法中的需求非常关键。使用数组跟踪出现次数可能导致效率问题,尤其是当元素范围很大或不是从0开始连续时,会有大量空间浪费或索引问题。哈希表提供了更灵活和空间高效的方式来处理这些问题。
🦆
在保持原始顺序的过程中,如果数组中存在重复的最大元素,如何确保选择正确的元素以最大化子序列的和?
算法通过哈希表中记录的元素出现次数来确保选择正确。即使元素是重复的,哈希表会记录每个元素应该出现的次数。遍历原始数组时,按照元素在数组中的顺序和哈希表中记录的次数来选择元素,这样可以确保即使是重复的元素也能正确地按照其出现次数被选择,从而最大化子序列的和。
🦆
在实际实现中,如何处理nums数组为空或k为0的特殊情况?
如果nums数组为空或k为0,按照这种情况直接返回一个空列表即可。这是因为没有元素可选择,或者不需要选择任何元素来组成子序列。这种边界情况的处理是算法的一部分,确保算法的鲁棒性和完整性。

相关问题