英文:
Why is a sliding window algorithm considered O(n) and not O(n^2)?
问题
在LeetCode上，有一个题目是424. Longest Repeating Character Replacement - (https://leetcode.com/problems/longest-repeating-character-replacement)。
题目描述如下：
给定一个字符串s和一个整数k。你可以选择字符串中的任意字符，并将其更改为任何其他大写英文字母。你最多可以执行k次操作。
返回在执行上述操作后，包含相同字母的最长子字符串的长度。
以下是我的解决方案：
func characterReplacement(s string, k int) int {
var out int
for i, _ := range s {
c := make(map[byte]int)
count := 0
for j:= i; j < len(s); j++ {
count +=1
c[s[j]] += 1
// determine max freq
maxFreq := 0
for _, v := range c {
if v > maxFreq {
maxFreq = v
}
}
if count - maxFreq <= k {
if count > out {
out = count
}
}
}
}
return out
}
除去determine max freq循环，这种滑动窗口算法被认为是O(n)的，但我不明白为什么是O(n)，在我看来应该是O(n^2)。
有人可以帮我理解为什么时间复杂度是O(n)而不是O(n^2)吗？
英文:
On leetcode 424. Longest Repeating Character Replacement -
(https://leetcode.com/problems/longest-repeating-character-replacement)
> You are given a string s and an integer k. You can choose any
> character of the string and change it to any other uppercase English
> character. You can perform this operation at most k times.
>
> Return the length of the longest substring containing the same letter
> you can get after performing the above operations.
Here's my solution:
func characterReplacement(s string, k int) int {
var out int
for i, _ := range s {
c := make(map[byte]int)
count := 0
for j:= i; j < len(s); j++ {
count +=1
c展开收缩] += 1
// determine max freq
maxFreq := 0
for _, v := range c {
if v > maxFreq {
maxFreq = v
}
}
if count - maxFreq <= k {
if count > out {
out = count
}
}
}
}
return out
}
Excluding the determine max freq loop, this type of sliding window algorithm is considered O(n), but I can't see why that is, to me it should be O(n^2).
Can someone help me understand why the time complexity is O(n) and not O(n^2)?
答案1
得分: 3
你实现的算法的复杂度是O(n^2)。如果你声称"这种类型的算法被认为是O(n)"，那么你没有正确实现这个算法。
这是一个O(n)的解决方案，用JavaScript编写（来源）：
var characterReplacement = function(s, k) {
// 保持对字符串中所有字符的计数
const chars = {}
// 左指针，当前最大频率的字符，返回值
let left = 0, maxf = 0, output = 0
for(let right = 0; right < s.length; right++) {
const char = s[right]
// 增加当前字符的计数
chars[char] = 1 + (chars[char] || 0)
// 更新字符频率
maxf = Math.max(maxf, chars[char])
// 缩小我们正在查看的字符窗口，直到我们可以有一个窗口，其中所有字符都相同+ k个要更改的字符
while((right-left+1) - maxf > k) {
chars[s[left]] -= 1
left++
}
// 如果当前窗口大于我们先前的最大窗口，则更新输出
output = Math.max(output, right - left +1)
}
return output
};
英文:
The way you implemented the algorithm, the complexity is O(n^2). If you claim that "this type of algorithm is considered O(n)", then you didn't correctly implement this algorithm.
Here is a O(n) solution for this problem, written in JavaScript (source):
var characterReplacement = function(s, k) {
// Keep count of all the characters in the string
const chars = {}
// left pointer, character with the current max frequency, return value
let left = 0, maxf = 0, output = 0
for(let right = 0; right < s.length; right++) {
const char = s[right]
// Increment count of the current character
chars[char] = 1 + (chars[char] || 0)
// Update the character frequency
maxf = Math.max(maxf, chars[char])
// Shrink the window of characters we are looking at until we can have a window of all the same characters + k charcters to change
while((right-left+1) - maxf > k) {
chars[s[left]] -= 1
left++
}
// Update the output if the current window is greater than our previous max window
output = Math.max(output, right - left +1)
}
return output
};
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论