সমস্যা বিবরণ
ফিক্সড লেঞ্থের ইন্টিজার অ্যারে দেওয়া আছে। প্রতিটি ০ কে ডুপ্লিকেট করতে হবে, বাকি উপাদানগুলো ডানে শিফট হবে। অ্যারের দৈর্ঘ্যের বাইরে যাওয়া উপাদানগুলো ড্রপ হবে।
উদাহরণ: [1,0,2,3,0,4,5,0] → [1,0,0,2,3,0,0,4] (শেষ ০ এবং ৫ ড্রপ হয়েছে)।
সমাধানের পদ্ধতি
- অ্যারেকপি করুন (arr2)।
- দুটি পয়েন্টার i (রেজাল্ট ইনডেক্স) এবং j (সোর্স ইনডেক্স) ব্যবহার করুন।
- যদি arr2[j] == 0:
- arr[i] = 0; i += 1
- যদি i < len(arr): arr[i] = 0; i += 1
- অন্যথায়: arr[i] = arr2[j]; i += 1; j += 1
- i < len(arr) পর্যন্ত চালিয়ে যান।
পাইথন উদাহরণ
class Solution(object):
def duplicateZeros(self, arr):
arr2 = arr[:]
i = j = 0
n = len(arr)
while i < n:
if arr2[j] == 0:
arr[i] = 0
i += 1
if i < n:
arr[i] = 0
j += 1
else:
arr[i] = arr2[j]
i += 1
j += 1
return arr
ob1 = Solution()
print(ob1.duplicateZeros([1,0,2,3,0,4,5,0]))
ইনপুট
[1,0,2,3,0,4,5,0]
আউটপুট
[1, 0, 0, 2, 3, 0, 0, 4]
O(1) স্পেস পদ্ধতি (দুই পাস)
def duplicateZeros(arr):
n = len(arr)
zeros = arr.count(0)
i = n - 1
j = n + zeros - 1
while i >= 0:
if j < n:
arr[j] = arr[i]
if arr[i] == 0:
j -= 1
if j < n:
arr[j] = 0
i -= 1
j -= 1
