了解 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中文網其他相關文章！