मान लीजिए हमारे पास 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 है।
समाधान दृष्टिकोण
यह स्लाइडिंग विंडो तकनीक का उपयोग करके हल किया जाता है। हम एक विंडो बनाए रखते हैं जहां सबसे अधिक बार आने वाले तत्व की गिनती + k >= विंडो आकार होता है।
- यदि
numsखाली है, तो 0 लौटाएं। - एक डिक्शनरी
num_countसे प्रत्येक नंबर की गिनती ट्रैक करें। max_count= विंडो में किसी भी नंबर की अधिकतम आवृत्ति।- विंडो का विस्तार करें (
endपॉइंटर)। यदिend - start + 1 > max_count + k, तो विंडो को सिकोड़ें (startपॉइंटर बढ़ाएं)। - अंत में
end - start + 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
