This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

preface

The fourth buckle is as follows:

A, thinking

The following two information can be learned from the question

  • Input: two arrays (positive order)
  • Output: median

So the easiest way to think about it is to combine the two arrays into one array and take the median

Second, the implementation

Code implementation

The complete code is shown below:

    /** * merge * time complexity O(m+n) */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] arr = new int[nums1.length + nums2.length];
        int index1 = 0;
        int index2 = 0;
        for (int i=0; i<arr.length; i++) {
            // Compare two arrays of elements, the smallest of which goes in
            if (index2 == nums2.length || (index1 < nums1.length && nums1[index1] <= nums2[index2])) {
                arr[i] = nums1[index1];
                index1 ++;
            } else{ arr[i] = nums2[index2]; index2++; }}// Get the median
        if (arr.length % 2= =0) {
            return ((double) arr[arr.length/2] + (double) arr[arr.length/2 - 1) /2;
        } else {
            return arr[arr.length/2]; }}Copy the code

The test code

The test code is shown below:

    public static void main(String[] args) {
        Number4 n = new Number4();
        int[] nums1 = {2.3};
        int[] nums2 = {1.4.5.7};
        double ret = n.findMedianSortedArrays(nums2, nums1);
        System.out.println("ret:" + ret);
    }
Copy the code

Third, summary

Today is the fourth buckle ~ this series will update the buckle 1-10 questions, continuous update for 10 days! Dig gold coin, I come 😁