পাইথনে সোর্টেড অ্যারে মার্জ (Merge Sorted Array)

দুটি সোর্টেড অ্যারে A এবং B দেওয়া থাকে। এগুলো মার্জ করে একটা সোর্টেড অ্যারে C বানাতে হবে। ইন-প্লেস শিফটিং ব্যবহার করা হয়েছে।

সমাধানের পদ্ধতি

1. i=0, j=0, end=len(A)-1 ইনিশিয়ালাইজ করুন।
2. end কে নন-জেরো এলিমেন্ট পর্যন্ত আনুন।
3. while j < len(B):
   • যদি i > end এবং A[i] খালি হয়, A[i] = B[j], j++।
   • অন্যথায় যদি A[i] > B[j], শিফট করুন, A[i] = B[j], end++, j++।
   • i++।
4. শিফট ফাংশন: শেষ থেকে i পর্যন্ত এলিমেন্ট এক ধাপ ডানে সরান।

উদাহরণ কোড

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        i = 0
        j = 0
        end = len(nums1) - 1
        while end >= 0 and not nums1[end]:
            end -= 1
        while j < len(nums2):
            if i > end and not nums1[i]:
                nums1[i] = nums2[j]
                j += 1
            elif nums1[i] > nums2[j]:
                self.shift(nums1, i)
                nums1[i] = nums2[j]
                end += 1
                j += 1
            i += 1
        return nums1

    def shift(self, num, i):
        j = len(num) - 1
        while not num[j]:
            j -= 1
        while j >= i:
            num[j + 1] = num[j]
            j -= 1

ob = Solution()
print(ob.merge([1,2,3,0,0,0], 3, [2,5,6], 3))

ইনপুট

[1,2,3,0,0,0] [2,5,6]

আউটপুট

[1, 2, 2, 3, 5, 6]