LeetCode 88 - Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array/

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/088_Merge_Sorted_Array.java

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = nums1.length - 1; i >= 0; i --) {
            if (m == 0 || (n > 0 && nums2[n - 1] > nums1[m - 1])) 
                nums1[i] = nums2[-- n];
            else nums1[i] = nums1[-- m];
        }

X.

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i > -1 && j > -1)
            nums1[k --] = (nums1[i] > nums2[j]) ? nums1[i --] : nums2[j --];
        while (j > -1) nums1[k --] = nums2[j --];
        return;
    }

https://leetcode.com/problems/merge-sorted-array/discuss/29522/This-is-my-AC-code-may-help-you

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

1. 第⼀一个array⻓长度是第⼆个的两倍，但是后⼀一半是空的
2. 三个sorted array
3. 跑了了不不少testcase；k个⽤用heap或者mergesort 时间空间复杂度计算
4. 目标可能没有足够空间
5. merge 2 sorted iterators，最后输出的是⼀一个新的iterator， 有hasNext
和next两个function
6. two infinite increasing integer stream
7. merge K sorted arrays, 唯⼀一就是告诉你数据量量可能很⼤大
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/Merge%20Sorted%20Arrays/MergeThreeSortedArrays.java

public class MergeThreeSortedArrays {
    public int[] merge(int[] a, int[] b, int[] c) {
        int[] ans = new int[a.length + b.length + c.length];
        int i = 0, j = 0, k = 0, cnt = 0;

        while (i < a.length && j < b.length && k < c.length) {
            ans[cnt ++] = Math.min(a[i], Math.min(b[j], c[k]));
            if (ans[cnt - 1] == a[i]) i ++;
            else if (ans[cnt - 1] == b[j]) j ++;
            else k ++;
        }

        while (i < a.length && j < b.length) {
            if (a[i] < b[j])
                ans[cnt ++] = a[i ++];
            else ans[cnt ++] = b[j ++];
        }

        while (i < a.length && k < c.length) {
            if (a[i] < c[k])
                ans[cnt ++] = a[i ++];
            else ans[cnt ++] = c[k ++];
        }

        while (j < b.length && k < c.length) {
            if (b[j] < c[k])
                ans[cnt ++] = b[j ++];
            else ans[cnt ++] = c[k ++];
        }

        while (i < a.length) ans[cnt ++] = a[i ++];
        while (j < b.length) ans[cnt ++] = b[j ++];
        while (k < c.length) ans[cnt ++] = c[k ++];
        return ans;
    }

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/Merge%20Sorted%20Arrays/MergeKSortedArrays.java

public class MergeKSortedArrays {

    class Array {
        int[] array;
        int index;
        Array(int[] array, int index) {
            this.array = array;
            this.index = index;
        }
    }

    public int[] merge(int[][] arrays) {
        PriorityQueue<Array> pq = new PriorityQueue<>(new Comparator<Array>() {
            public int compare(Array a, Array b) {
                return a.array[a.index] - b.array[b.index];
            }
        });
        for (int[] array : arrays) {
            if (array.length == 0) continue;
            pq.add(new Array(array, 0));
        }
        List<Integer> list = new ArrayList<>();
        while (!pq.isEmpty()) {
            Array cur = pq.poll();
            list.add(cur.array[cur.index]);
            if (++ cur.index < cur.array.length)
                pq.add(cur);
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i ++)
            ans[i] = list.get(i);
        return ans;
    }

Facebook Performance & Capacity Engineer Intern 面经
1. merge sort 的 merge 操作，目标可能没有足够空间

B里没有空间放下a中所有元素，别想太复杂

哦，那看样子就是说不能重用其中一个array

Facebook 脸书 莫名其妙跪经