了解 LeetCode 中的 K 元素模式：基础知识（第 1 部分）

我终于明白了！学习 LeetCode 的最好方法不是一遍又一遍地解决问题，有时要花一小时才能解决它们，效率很低。掌握 LeetCode 的关键是学习模式。我们来研究一下常见的吧！

面试官喜欢询问有关查找、维护或操作字符串或数组中的 K 个元素的问题。起初，我认为每个问题都是完全不同的，但后来我开始看到其中的联系。让我通过两个真正帮助我理解这种模式的问题来向您展示我的意思。

问题 1：找到长度为 K 且和最大的子序列

从技术上讲，这是一个“简单”级别的问题（仅由一家公司提出），但是，它教会了您如何思考这些 k 元素问题！

他们在问什么

你得到一个数字数组和一个值 k，你需要从数组中找到 k 个数字，使其总和达到最大可能值。但是（这就是一开始让我绊倒的部分），你必须保持数字的原始顺序！

示例：

哦！这个比较棘手：

好的，我明白了

一开始，我想“只要抓住 k 个最大的数字，就完成了！”但不——订单要求改变了一切。最后点击的是：

1. 我们需要记住每个数字的来源，对吧？所以 我想，“我应该将每个数字与它配对 位置？”

1. 然后我们可以按值对这些对进行排序（即 每对中的第一个数字），但我们正在跟踪 他们来自哪里（这是第二个数字）！

1. 现在最酷的部分 - 我们只需要 k 个，所以抓住 前 k 对并保持其位置：

1. 最后遍历原始数组，只保留 位置在我们集合中的数字：

这是代码

2：流中的第 K 个最大元素

好吧，所以这个问题也被标记为“简单”（有五家公司提出要求），但是这个问题对我来说比任何更困难的 K 元素问题都更令人困惑。

他们在问什么

想象一下您在一所大学工作，学生不断提交考试成绩。你的工作是随时知道第 k 个最高分。新的分数不断出现，您需要跟踪。

他们给你 k 和一些初始分数，然后他们不断地向你抛出新的分数，并且每次都想知道第 k 个最高分数。让我们看一个例子：

好的，我想我明白了

起初，每次有新分数进来时，我都会尝试对整个数组进行排序，但我知道排序可能效率很低。然后我想，当我只关心前 k 名时，为什么要跟踪所有分数呢？

这是我的分解方法：

1. 首先，对初始分数进行排序，只保留前k个：

1. 现在当新的分数出现时：

如果它小于我们的第 k 个最高值（第一个数字），请忽略它
如果它更大，它就属于我们列表中的某个位置

以下是每次添加时发生的情况：

守则

为什么这两个问题是相关的

这两个问题都教会了我一些关于处理 k 元素的非常重要的知识：

• 第一个问题：有时你需要跟踪元素在哪里 来自
• 第二个问题：有时只需要保留k个元素 周围

这些 k 元素问题都是关于如何巧妙地处理保留哪些信息以及丢弃哪些信息。
下次我们将研究基于这些想法的另外两个 k 元素问题。我希望最后你能看到一个模式，并且这些类型的问题看起来不那么可怕！

以上是了解 LeetCode 中的 K 元素模式：基础知识（第 1 部分）的详细内容。更多信息请关注PHP中文网其他相关文章！