สมมติว่าเรามีรายการที่เรียกว่า nums และค่า k ตอนนี้ให้เราพิจารณาการดำเนินการที่เราสามารถอัปเดตค่าของตัวเลขใดๆ ในรายการได้ เราต้องหาความยาวของรายการย่อยที่ยาวที่สุดซึ่งมีตัวเลขซ้ำกันหลังจากดำเนินการสูงสุด k ครั้ง
ดังนั้น ถ้าอินพุตเป็น nums =[8, 6, 6, 4, 3, 6, 6] k =2 ผลลัพธ์จะเป็น 6 เพราะเราสามารถเปลี่ยน 4 และ 3 เป็น 6 เพื่อสร้างอาร์เรย์นี้ [ 8, 6, 6, 6, 6, 6, 6] และความยาวของรายการย่อยที่มีทั้งหมด 6s คือ6
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ถ้าตัวเลขว่างก็
-
คืนค่า 0
-
-
num_count :=แผนที่ว่างเปล่า
-
max_count :=0
-
เริ่ม :=0
-
สำหรับแต่ละดัชนีสิ้นสุดและค่า num เป็น num ให้ทำ
-
num_count[num] :=num_count[num] + 1
-
max_count :=สูงสุดของ max_count และ num_count[num]
-
ถ้าสิ้นสุด - start + 1> max_count + k แล้ว
-
num_count[nums[start]] :=num_count[nums[start]] - 1
-
start :=start + 1
-
-
-
กลับสิ้นสุด - เริ่ม + 1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
from collections import defaultdict
def solve(nums, k):
if not nums:
return 0
num_count = defaultdict(int)
max_count = 0
start = 0
for end, num in enumerate(nums):
num_count[num] += 1
max_count = max(max_count, num_count[num])
if end - start + 1 > max_count + k:
num_count[nums[start]] -= 1
start += 1
return end - start + 1
nums = [8, 6, 6, 4, 3, 6, 6]
k = 2
print(solve(nums, k)) อินพุต
[8, 6, 6, 4, 3, 6, 6], 2
ผลลัพธ์
6
