字典應用: 第k個出現一次的字串 Kth Distinct String in an Array_LC #2053

閱讀時間約 3 分鐘

題目敘述 Kth Distinct String in an Array

給定一個輸入陣列arr 和 參數k

請返回第k個出現恰好一次的陣列元素


測試範例

Example 1:

Input: arr = ["d","b","c","b","c","a"], k = 2
Output: "a"
Explanation:
The only distinct strings in arr are "d" and "a".
"d" appears 1st, so it is the 1st distinct string.
"a" appears 2nd, so it is the 2nd distinct string.
Since k == 2, "a" is returned.

Example 2:

Input: arr = ["aaa","aa","a"], k = 1
Output: "aaa"
Explanation:
All strings in arr are distinct, so the 1st string "aaa" is returned.

約束條件

Constraints:

  • 1 <= k <= arr.length <= 1000

1 <= 參數k值 <= 輸入陣列長度 <= 一千

  • 1 <= arr[i].length <= 5

每個陣列元素的長度介於1~5之間。

  • arr[i] consists of lowercase English letters.

陣列元素只會有小寫英文字母組成的字串。


演算法 字典統計每個出現次數


建立一個字典。

掃描每個陣列元素,統計每個陣列元素的出現次數。

每遇到一個出現一次的陣列元素,k值就減一

當k值等於零的時候,當下的元素就是第k個恰好出現一次的陣列元素


程式碼 字典統計每個出現次數

class Solution:
def kthDistinct(self, arr: List[str], k: int) -> str:

# key: unique string
# value: occurrence
str_occ_dict = Counter(arr)

for element in arr:

if str_occ_dict[element] == 1:
# find one distinct string, subtract counter k with 1
k -= 1

if k == 0:
# kth distinct string is current element
return element

return ""

複雜度分析

時間複查度: O(n)

從左到右掃描每個陣列元素,所需時間為O(n)


空間複查度: O(n)

建立一個字典,儲存每個陣列元素的出現次數,最多所需空間為O(n)


Reference

[1] Kth Distinct String in an Array - LeetCode

avatar-img
90會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目敘述 Make Two Arrays Equal by Reversing Subarrays 題目給定兩個輸入陣列,請問能否透過子陣列的反轉讓兩個陣列相等? 子陣列的反轉操作次數不受限制。 如果可以,返回True 如果不行,返回False
題目敘述 Number of Senior Citizens 給定一個旅客的車票字串陣列,美個字串的最後第四個和第三個數字代表旅客的年齡。 例如: XXX...XXX2015 代表旅客年齡為20歲。 總請計算共有多少位乘客的年齡 > 60 歲
題目要求計算兩個二進位字串的相加,並以字串的形式輸出。 字串內容只包含'0'或'1'字元。 複雜度分析 時間複雜度為O(m+n),空間複雜度為O(m+n)。
給定木板的長度和切割點位置,找到最小總切割成本。透過DP動態規劃和區間DP框架,定義DP狀態並推導出最小切割成本的遞迴關係式。複雜度分析為時間複雜度O(n^3)和空間複雜度O(n^2)。關鍵知識點在於挖掘切割問條的共通模式,透過範例和圖解輔助思考。
給定一個9x9的輸入陣列代表數獨題目已經 部分作答 的狀態, 請驗證已經作答的部分是否為合法的Sudoku的輸入。 註: 合法的Sudoku輸入必須滿足這些規則 1~9每一直排恰好出現一次。 1~9每一橫排恰好出現一次。 1~9在3x3的小方陣裏恰好出現一次。
題目敘述 Minimum Deletions to Make String Balanced 給定一個只會有包含'a'b或'b'的輸入字串s。 每次操作可以任選一個字元刪除。 請問最少需要多少次操作,才會使得所有的'b'都在'a'後面? 測試範例 Example 1: Input: s
題目敘述 Make Two Arrays Equal by Reversing Subarrays 題目給定兩個輸入陣列,請問能否透過子陣列的反轉讓兩個陣列相等? 子陣列的反轉操作次數不受限制。 如果可以,返回True 如果不行,返回False
題目敘述 Number of Senior Citizens 給定一個旅客的車票字串陣列,美個字串的最後第四個和第三個數字代表旅客的年齡。 例如: XXX...XXX2015 代表旅客年齡為20歲。 總請計算共有多少位乘客的年齡 > 60 歲
題目要求計算兩個二進位字串的相加,並以字串的形式輸出。 字串內容只包含'0'或'1'字元。 複雜度分析 時間複雜度為O(m+n),空間複雜度為O(m+n)。
給定木板的長度和切割點位置,找到最小總切割成本。透過DP動態規劃和區間DP框架,定義DP狀態並推導出最小切割成本的遞迴關係式。複雜度分析為時間複雜度O(n^3)和空間複雜度O(n^2)。關鍵知識點在於挖掘切割問條的共通模式,透過範例和圖解輔助思考。
給定一個9x9的輸入陣列代表數獨題目已經 部分作答 的狀態, 請驗證已經作答的部分是否為合法的Sudoku的輸入。 註: 合法的Sudoku輸入必須滿足這些規則 1~9每一直排恰好出現一次。 1~9每一橫排恰好出現一次。 1~9在3x3的小方陣裏恰好出現一次。
題目敘述 Minimum Deletions to Make String Balanced 給定一個只會有包含'a'b或'b'的輸入字串s。 每次操作可以任選一個字元刪除。 請問最少需要多少次操作,才會使得所有的'b'都在'a'後面? 測試範例 Example 1: Input: s
你可能也想看
Google News 追蹤
Thumbnail
Hi 我是 VK~ 在 8 月底寫完〈探索 AI 時代的知識革命:NotebookLM 如何顛覆學習和創作流程?〉後,有機會在 INSIDE POSSIBE 分享兩次「和 NotebookLM 協作如何改變我學習和創作」的主題,剛好最近也有在許多地方聊到關於 NotebookLM 等 AI 工具
Thumbnail
這是張老師的第三本書,我想前二本應該也有很多朋友們都有讀過,我想絕對是受益良多,而這次在書名上就直接點出,著重在從投資的角度來切入
Thumbnail
題目敘述 Make Two Arrays Equal by Reversing Subarrays 題目給定兩個輸入陣列,請問能否透過子陣列的反轉讓兩個陣列相等? 子陣列的反轉操作次數不受限制。 如果可以,返回True 如果不行,返回False
Thumbnail
題目敘述 Sort Array by Increasing Frequency Leetcode #1636 給定一個輸入陣列,請依照出現頻率的多寡從低頻到高頻排列陣列元素。 如果有兩個元素的出現頻率相同,依照元素大小從大到小排列。 測試範例 Example 1: Input: nums
Thumbnail
題目敘述 Intersection of Two Arrays II 給定兩個輸入陣列,請找出兩個陣列交集的元素,並且依照出現次數輸出。 測試範例 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] 交集元素
Thumbnail
題目敘述 Minimum Increment to Make Array Unique 給定一個整數陣列,每回合可以任意挑一個數字進行+1的加法操作。 請問最少需要多少次的+1加法操作,才能讓每個數字都相異?
Thumbnail
題目敘述 Subarray Sums Divisible by K 給定一個整數陣列,請計算有幾個區間和能夠整除k的連續區間? 測試範例 Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7
Thumbnail
給定一個字串陣列,請把它們所共有的字元伴隨著出現次數輸出。這篇文章介紹如何使用字典統計出現次數,和字典取交集的方法來解決此問題。並提供了複雜度分析和關鍵知識點。
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,和一個指定的k值。 請問,在輸入陣列nums中,有幾個子陣列的元素總合恰好為k ? 例如: nums = [1,2,3], k = 3 則有兩個子陣列的元素總合為3,分別是[1,2] 和 [3] 如果是第一次聽到或接觸前綴和prefix的同學
Thumbnail
題目敘述 題目會給定一個整數陣列arr,要求我們判斷是否每個元素的出現次數都不同? 題目的原文敘述 測試範例 Example 1: Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurre
Thumbnail
Hi 我是 VK~ 在 8 月底寫完〈探索 AI 時代的知識革命:NotebookLM 如何顛覆學習和創作流程?〉後,有機會在 INSIDE POSSIBE 分享兩次「和 NotebookLM 協作如何改變我學習和創作」的主題,剛好最近也有在許多地方聊到關於 NotebookLM 等 AI 工具
Thumbnail
這是張老師的第三本書,我想前二本應該也有很多朋友們都有讀過,我想絕對是受益良多,而這次在書名上就直接點出,著重在從投資的角度來切入
Thumbnail
題目敘述 Make Two Arrays Equal by Reversing Subarrays 題目給定兩個輸入陣列,請問能否透過子陣列的反轉讓兩個陣列相等? 子陣列的反轉操作次數不受限制。 如果可以,返回True 如果不行,返回False
Thumbnail
題目敘述 Sort Array by Increasing Frequency Leetcode #1636 給定一個輸入陣列,請依照出現頻率的多寡從低頻到高頻排列陣列元素。 如果有兩個元素的出現頻率相同,依照元素大小從大到小排列。 測試範例 Example 1: Input: nums
Thumbnail
題目敘述 Intersection of Two Arrays II 給定兩個輸入陣列,請找出兩個陣列交集的元素,並且依照出現次數輸出。 測試範例 Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] 交集元素
Thumbnail
題目敘述 Minimum Increment to Make Array Unique 給定一個整數陣列,每回合可以任意挑一個數字進行+1的加法操作。 請問最少需要多少次的+1加法操作,才能讓每個數字都相異?
Thumbnail
題目敘述 Subarray Sums Divisible by K 給定一個整數陣列,請計算有幾個區間和能夠整除k的連續區間? 測試範例 Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7
Thumbnail
給定一個字串陣列,請把它們所共有的字元伴隨著出現次數輸出。這篇文章介紹如何使用字典統計出現次數,和字典取交集的方法來解決此問題。並提供了複雜度分析和關鍵知識點。
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,和一個指定的k值。 請問,在輸入陣列nums中,有幾個子陣列的元素總合恰好為k ? 例如: nums = [1,2,3], k = 3 則有兩個子陣列的元素總合為3,分別是[1,2] 和 [3] 如果是第一次聽到或接觸前綴和prefix的同學
Thumbnail
題目敘述 題目會給定一個整數陣列arr,要求我們判斷是否每個元素的出現次數都不同? 題目的原文敘述 測試範例 Example 1: Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurre