Question

IN JAVA PLEASE This problem requires you to code the Merge part of the Merge Sort algorithm. The Merge step merges n elements which takes O(n) time. Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Any code that is found to exceed linear time will fail the tests.

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

import java.util.Scanner;
import java.util.ArrayList;

public class Solution {
public void merge(int [] nums1, int m, int [] nums2, int n){
//Add code below
}
public static void main(String [] args) {
//Variables
Scanner scnr = new Scanner(System.in);
ArrayList<Integer> arrList = new ArrayList<Integer>();
int [] arr1, arr2;
int split = 0;
Solution test = new Solution();
//Remaining values will be added to the array
while(scnr.hasNext()){
arrList.add(scnr.nextInt());
//Get position to mark end of arr1 and beginning of arr2
if(arrList.size() >= 2 && arrList.get(arrList.size()-1) <= arrList.get(arrList.size()-2))
split = arrList.size()-1;
}
//Instance primitive array to size of ArrayList
arr1 = new int[arrList.size()];
arr2 = new int[arrList.size()-(split)];
//Copy elements from ArrayList to primitive array
for(int i = 0; i < (split); i++)
arr1[i] = arrList.get(i);
for(int i = 0; i < arrList.size()-(split); i++)
arr2[i] = arrList.get(split+i);
//Test values
test.merge(arr1,split,arr2,arrList.size()-(split));
//Prints elements in arr1 after merge
for(int i : arr1)
System.out.println(i);
}
}

Answer 1

import java.util.Scanner;
import java.util.ArrayList;

public class Solution {
    public void merge(int nums1[], int m, int nums2[], int n){
        int i = 0,j = 0,k = 0;
        int arr[] = new int[m+n];
        while(i<m && j<n){
            if(nums1[i] <= nums2[j]){
                arr[k++] = nums1[i++];
            }
            else {
                arr[k++] = nums2[j++];
            }
        }
        while (i<m){
            arr[k++] = nums1[i++];
        }
        while (j<n){
            arr[k++] = nums2[j++];
        }
        for(int t = 0;t<arr.length;t++){
            nums1[t] = arr[t];
        }
    }

    public static void main(String [] args) {
//Variables
        Scanner scnr = new Scanner(System.in);
        ArrayList<Integer> arrList = new ArrayList<Integer>();
        int [] arr1, arr2;
        int split = 0;
        Solution test = new Solution();
//Remaining values will be added to the array
        while(scnr.hasNext()){
            arrList.add(scnr.nextInt());
//Get position to mark end of arr1 and beginning of arr2
            if(arrList.size() >= 2 && arrList.get(arrList.size()-1) <= arrList.get(arrList.size()-2))
                split = arrList.size()-1;
        }
//Instance primitive array to size of ArrayList
        arr1 = new int[arrList.size()];
        arr2 = new int[arrList.size()-(split)];
//Copy elements from ArrayList to primitive array
        for(int i = 0; i < (split); i++)
            arr1[i] = arrList.get(i);
        for(int i = 0; i < arrList.size()-(split); i++)
            arr2[i] = arrList.get(split+i);
//Test values
        test.merge(arr1,split,arr2,arrList.size()-(split));
//Prints elements in arr1 after merge
        for(int i : arr1)
            System.out.println(i);
    }
}