سوال 88

عنوان سوال : Valid Anagram

• آسان
• مرتب سازی
• دو اشاره گر
• آرایه

---

دو آرایهٔ عدد صحیح nums1 و nums2 داده شده‌اند که هر دو به‌صورت صعودی (non-decreasing) مرتب شده‌اند.
دو عدد صحیح m و n نیز تعداد عناصر معتبر موجود در nums1 و nums2 را مشخص می‌کنند.

هدف این است که آرایهٔ nums2 در nums1 ادغام شود تا یک آرایهٔ مرتب‌شدهٔ واحد تشکیل شود.
خروجی نباید برگردانده شود، بلکه باید در همان آرایهٔ nums1 ذخیره شود.

آرایهٔ nums1 طولی برابر با m + n دارد که:

• m عنصر اول داده‌های اصلی هستند.
• n عنصر آخر مقدارشان 0 است و باید نادیده گرفته شوند.

آرایهٔ nums2 نیز دقیقاً n عنصر دارد.

---

مثال ۱:

ورودی:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

خروجی:
[1,2,2,3,5,6]

توضیح:
دو آرایهٔ در حال ادغام: [1,2,3] و [2,5,6]
نتیجهٔ ادغام: [1,2,2,3,5,6]

---

مثال ۲:

ورودی:
nums1 = [1], m = 1
nums2 = [], n = 0

خروجی:
[1]

توضیح:
ادغام [1] و [] برابر با [1] است.

---

مثال ۳:

ورودی:
nums1 = [0], m = 0
nums2 = [1], n = 1

خروجی:
[1]

توضیح:
چون m = 0، هیچ عنصری در nums1 وجود ندارد.
مقدار 0 فقط برای ایجاد ظرفیت کافی قرار داده شده است.

---

محدودیت‌ها:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

راه حل

public void Merge(int[] nums1, int m, int[] nums2, int n)
{
    var i = m - 1;
    var j = n - 1;
    var k = m + n - 1;

    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }
}