Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Topic describes

Given two positive-ordered (from small to large) arrays of size m and n, nums1 and nums2. Please find and return the median of the two positive ordinal groups.

Idea 1: Merge binary
  1. Using the merge idea, two arrays are ordered, which is the last step of merge sort, where you just iterate through the left and right arrays and put them into the new array.
  2. The first while is when neither array subscript is out of bounds:
    1. Both arrays are compared from left to right, the smaller one is put in the new array, subscript plus one for the next round of comparison,
    2. Exit the loop when one of the arrays is out of bounds and one of the arrays is done,
    3. So the next two are only going to do one, which is the unfetched array, and we’re going to walk through it into the new array, and we’re done sorting.
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length, l2 = nums2.length;
        int l3 = l1+l2;
        int[] ans = new int[l3];
        int i = 0, j = 0, k = 0;
        while (i < l1 && j < l2) {
            ans[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        }
        while (i < l1) {
            ans[k++] = nums1[i++];
        }
        while (j < l2) {
            ans[k++] = nums2[j++];
        }
        double num = 0;
        if (l3 % 2= =0) {
            num =  (double)(ans[l3/2] + ans[l3/2-1) /2;
        } else {
            num = (double)ans[l3/2];
        }
        returnnum; }}Copy the code
Idea 2: Dual Pointers
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] result = new int[(nums1.length+nums2.length)];
        int k = 0;
        // create two variables p and q to act as Pointers
        int p = 0, q = 0;
        while (p<nums1.length && q<nums2.length){
            if (nums1[p] <= nums2[q]){
                result[k] = nums1[p];
                k++;
                p++;
            } else{ result[k] = nums2[q]; k++; q++; }}// Fill in the remaining array elements
        while(p ! = nums1.length){ result[k] = nums1[p]; k++; p++; }while(q ! = nums2.length){ result[k] = nums2[q]; k++; q++; }int length = result.length;
        if (length % 2= =0) {return (double)(result[length/2] + result[length/2-1) /2;
        } else {
            return (double)result[length/2]; }}}Copy the code