package leetcode;

import java.util.Arrays;

/**
 * @author: vince_zww
 * @date: 2019/8/29 18:41
 * @desceription:
 * 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
 *
 *说明:
 *
 *初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
 *你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
 *示例:
 *
 *输入:
 *nums1 = [1,2,3,0,0,0], m = 3
 *nums2 = [2,5,6],       n = 3
 *
 *输出: [1,2,2,3,5,6]
 */
public class LeetCode_88 {

    public static void main(String[] args) {
        int[] nums1 ={1,2,3,0,0,0};
        int m = 3;
        int[] nums2 ={2,5,6};
        int n = 3;
        System.out.println(Arrays.toString(merge1(nums1,m,nums2,n)));
        System.out.println(Arrays.toString(merge2(nums1,m,nums2,n)));
        System.out.println(Arrays.toString(merge3(nums1,m,nums2,n)));
    }

    /**
     * 数组解决方案
     * 自己思考的方案，确实比较臃肿
     */
    private static int[] merge1(int[] nums1, int m, int[] nums2, int n) {
        for (int l = 0; l < n; l++) {
            int num2 = nums2[l];
            for (int i = 0; i < nums1.length; i++) {
                if (num2 < nums1[i]) {
                    int j = i;
                    int k = nums1.length;
                    while (k > j) {
                        if ((k - 2) >= 0) {
                            nums1[k - 1] = nums1[k - 2];
                            k--;
                        } else {
                            break;
                        }
                    }
                    nums1[i] = num2;
                    m++;
                    break;
                }
                if(i>=m){
                    nums1[m]=num2;
                    m++;
                    break;
                }
            }
        }
        return nums1;
    }

    /**
     * 讨论区解决方案
     *
     */
    private static int[] merge2(int[] nums1, int m, int[] nums2, int n) {
        if(nums1 == null || nums2 == null || m < 0 || n<= 0){
            return nums1;
        }
        //从后往前
        int index1 = nums1.length - 1;
        int index2 = nums2.length - 1;
        while(m >= 0 && index2 >= 0){
            if(m == 0){
                nums1[index1--] = nums2[index2--];
            }
            else{
                if(nums2[index2] > nums1[m- 1]){
                    nums1[index1--] = nums2[index2--];
                }
                else{
                    nums1[index1--] = nums1[--m];
                }
            }
        }
        return nums1;
    }

    /**
     * 官方解决方案
     * 直接使用内置函数，简单又方便
     */
    private static int[] merge3(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
        return nums1;
    }

}