Merge Sorted Array

Leetcode #88 | Easy | Два указателя | Указатель на запись

Идея

Три указателя, сливаем с конца. Первый указатель на конец первого m-1, второй на n-1, третий указатель - указатель на запись - n+m-1. Цикл while пока p2>=0. Если элемент из первого больше пишем его по write, иначе пишем из второго и двигаем соответствующие указатели, в конце двигаем write.

Big-O

• Время O(N+M)
• Память O(1)

Код

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1, w = m + n - 1;
        while (p2 >= 0) {
            if (p1 >= 0 && nums1[p1] > nums2[p2]) nums1[w--] = nums1[p1--];
            else nums1[w--] = nums2[p2--];
        }
    }
}