Merge Sorted Array

صورت مسئله: دو آرایه‌ی مرتب صعودی nums1 و nums2 به همراه دو عدد m و n داده شده است. آرایه‌ی nums1 طول کل m + n دارد: m عنصر اول آن معتبر و مرتب هستند و عناصر باقی‌مانده (بعد از اندیس m-1) فضای خالی‌اند (پرکننده، معمولاً صفر، ولی مقدارشان بی‌اهمیت است). آرایه‌ی nums2 دقیقاً n عنصر دارد و مرتب صعودی است. nums2 را داخل nums1 ادغام کنید طوری که در پایان nums1 یک آرایه‌ی مرتب صعودی به طول m + n شود. این کار باید درجا (in-place) انجام شود؛ تابع هیچ مقداری برنمی‌گرداند و داور پس از فراخوانی کل محتوای nums1 را بررسی می‌کند.

ورودی: تابعی با پارامترهای nums1: List[int] (به طول m+n)، m: int، nums2: List[int] (به طول n)، n: int.

خروجی: هیچ (تغییر درجا در nums1).

قیود:

• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9
• len(nums1) == m + n و len(nums2) == n
• m عنصر اول nums1 و تمام عناصر nums2 مرتب صعودی هستند
• مقادیر بعد از اندیس m در nums1 پرکننده‌اند و نباید مورد استفاده قرار بگیرند (هر مقداری می‌توانند داشته باشند)

مثال‌ها:

1. nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3 → nums1=[1,2,2,3,5,6]
2. nums1=[1], m=1, nums2=[], n=0 → nums1=[1] (بدون تغییر)
3. nums1=[0], m=0, nums2=[1], n=1 → nums1=[1]

نکات مهم:

• حالت‌های m=0 (تمام nums1 از nums2 پر می‌شود) و n=0 (هیچ چیزی ادغام نمی‌شود) باید پشتیبانی شوند.
• راه‌حل باید از پرکننده‌ها نادیده بگیرد: در مثال nums1=[1,2,3,4], m=3, nums2=[5], n=1 عدد 4 پرکننده است و باید بازنویسی شود؛ پاسخ [1,2,3,5] است.

پیچیدگی هدف: O(m+n) زمان با ادغام از انتها به ابتدا (سه اشاره‌گر)، O(1) حافظه اضافه. ادغام از ابتدا که نیازمند جابه‌جایی مکرر عناصر O((m+n)^2) می‌شود و باید رد شود.