合并两个有序数组「变题」

88. 合并两个有序数组

// 技巧：从后向前
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int k = m + n - 1;
    int i = m - 1, j = n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] >= nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    while (i >= 0) nums1[k--] = nums1[i--];
    while (j >= 0) nums1[k--] = nums2[j--];
}

变题一：要求去重

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int k = m + n - 1, prev = nums1[m - 1] + nums2[n - 1] + 1;
    int i = m - 1, j = n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] >= nums2[j]) {
            if (nums1[i] == prev) i--;
            else {
                nums1[k] = nums1[i--];
                prev = nums1[k--];
            }
        } else {
            if (nums2[j] == prev) j--;
            else {
                nums1[k] = nums2[j--];
                prev = nums1[k--];
            }
        }

    }
    while (i >= 0) {
        if (nums1[i] == prev) i--;
        else {
            nums1[k] = nums1[i--];
            prev = nums1[k--];
        }
    }
    while (j >= 0) {
        if (nums2[j] == prev) i--;
        else {
            nums1[k] = nums2[j--];
            prev = nums1[k--];
        }
    }
    System.out.println(m + n - k - 1);
    for (i = k + 1; i < m + n; i++) {
        nums1[i - k - 1] = nums1[i];
    }
}

变题二：合并 K 个有序数组

// 时间复杂度 : O(nlogk)
// 空间复杂度 : O(n) -> 若不算返回数组 O(k)
public int[] merge(int[][] nums) {
    int idx = 0, n = 0;
    for (int i = 0; i < nums.length; i++) n += nums[i].length;
    int[] ans = new int[n];
    Queue<int[]> q = new PriorityQueue<>((a, b) -> nums[a[0]][a[1]] - nums[b[0]][b[1]]);
    for (int i = 0; i < nums.length; i++) {
        if (nums[i].length != 0) q.offer(new int[]{i, 0});
    }
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        ans[idx++] = nums[cur[0]][cur[1]];
        if (cur[1] + 1 < nums[cur[0]].length) q.offer(new int[]{cur[0], cur[1] + 1});
    }
    return ans;
}
// 调用过程
int[] arr = merge(new int[][]{
    {2, 3, 6},
    {1, 4, 5, 7, 9},
    {2, 8, 10}
});

变题三：合并 K 个有序数组并去重

直接在变题二的基础上修改即可！

public int[] merge(int[][] nums) {
    int idx = 0, n = 0;
    for (int i = 0; i < nums.length; i++) n += nums[i].length;
    int[] ans = new int[n];
    Queue<int[]> q = new PriorityQueue<>((a, b) -> nums[a[0]][a[1]] - nums[b[0]][b[1]]);
    for (int i = 0; i < nums.length; i++) {
        if (nums[i].length != 0) q.offer(new int[]{i, 0});
    }
    int prev = nums[q.peek()[0]][q.peek()[1]] - 1;
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        // 修改部分
        if (prev != nums[cur[0]][cur[1]]) {
            ans[idx++] = nums[cur[0]][cur[1]];
            prev = nums[cur[0]][cur[1]];
        }
        if (cur[1] + 1 < nums[cur[0]].length) q.offer(new int[]{cur[0], cur[1] + 1});
    }
    return ans;
}