Link Title:
Force buckle

Title Description

Give two positively ordered (from small to large) arrays nums1 and nums2 of sizes m and n, respectively.
Please find and return the median of these two positive arrays. The time complexity of the algorithm should be O(log (m+n))

Topic analysis

Conventional thinking:
1. Merge two arrays in sorting, time complexity O(m+n), space complexity O(m+n)
2. Merge sort, time complexity O(m+n), space complexity O(m+n)
How should we solve this problem?

According to the time complexity of the problem, you can consider using binary search, which is also the difficulty of the problem.

Suppose that the two ordered arrays are A and B respectively, and the total length of the two arrays is totalLength:

• The total length of the two groups is odd: median subscript (midIndex)=totalLength/2, median = the number of subscript midIndex;
• The total length of the two groups is an even number. The median subscript has two midIndex1, midIndex2, midIndex1=totalLength/2-1, midIndex2=totalLength/2, and the median = (the number of subscript midIndex1 + the number of subscript midIndex2) / 2;

Note: midIndex is the subscript of two arrays after merging. It does not really merge the two arrays. We should understand this concept.

At this time, the problem is to find the k-th element in arrays A and B. how to find it?
You can compare A[k/2-1] with B[k/2-1]:

• A[k/2 − 1] < = B [k/2 − 1], then in array a, the elements with subscripts 0 to k/2 − 1 are smaller than klelement, and these elements can be excluded;
• A[k/2 − 1] > b [k/2 − 1], then the elements with subscripts 0 to k/2 − 1 in array B are smaller than klelement, and these elements can be excluded;

It is easy to think that the search range is reduced by half. You can continue the binary search on the excluded new array, and reduce the value of k according to the number of excluded numbers (because the number of excluded numbers is not greater than the smallest number of k). Attention should be paid to the following situations:

1. Ensure that the array does not cross the boundary;

2. If an array is empty, all elements in the array are excluded. We can directly return the k-th smallest element in another array;

3. If k=1, just return the minimum value of the first element of the two arrays.

code implementation

• Time complexity: O(log (m+n))
• Space complexity: O(1)

public class FindMedianSortedArrays_4 {


    /**
     * Conventional thinking:
     * <1>Merge two arrays in sort
     * <2>Merge sort
     *
     * @param args
     */

    public static void main(String[] args) {
        int[] num1 = {1, 3};
        int[] num2 = {2};
        //int[] num1 = {1, 3,4,9};
        //int[] num2 = {1,2,3,4,5,6,7,8,9};
        FindMedianSortedArrays_4 findMedianSortedArrays_4 = new FindMedianSortedArrays_4();
        findMedianSortedArrays_4.findMedianSortedArrays(num1, num2);

    }


    /**
     * Binary search, ingenious
     * Time complexity: O(log (m+n))
     * Space complexity: O(1)
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int totalLength = length1 + length2;


        // The total length of the two groups is odd, the median subscript (midIndex)=totalLength/2, and the median = the number of subscripts k
        if (totalLength % 2 == 1) {
            System.out.println("Total length of two groups( totalLength)Odd number");
            int midIndex = totalLength / 2;

            double median = getKthElement(nums1, nums2, midIndex + 1);
            System.out.println("median:" + median);
            return median;

        } else {
            // The total length of the two groups is even, and the median subscript has two midIndex1, midIndex2, midIndex1=totalLength/2-1, midIndex2=totalLength/2,
            // Median = (number of subscript midIndex1 + number of subscript midIndex2) / 2
            System.out.println("Total length of two groups( totalLength)Even number");

            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            System.out.println("median:" + median);

            return median;

        }
    }

    /**
     * Gets the k-th smallest element
     *
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */
    public int getKthElement(int[] nums1, int[] nums2, int k) {
        System.out.println("initial k:" + k);

        int length1 = nums1.length;
        int length2 = nums2.length;


        // Used to record two arrays and find the starting subscript of the k-th small element
        int index1 = 0, index2 = 0;


        while (true) {
            // In the boundary case, array 1 is empty, and only array 2 needs to be considered
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            // In the boundary case, array 2 is empty, and only array 1 needs to be considered
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }

            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            // Compare num1[k/2-1] with num1[k/2-1]
            int compareIndex1 = Math.min(index1 + k / 2, length1) - 1;
            int compare1 = nums1[compareIndex1];
            int compareIndex2 = Math.min(index2 + k / 2, length2) - 1;
            int compare2 = nums2[compareIndex2];

            if (compare1 < compare2) {

                k -= compareIndex1 - index1 + 1;

                index1 = compareIndex1 + 1;


            } else {
                k -= compareIndex2 - index2 + 1;
                index2 = compareIndex2 + 1;

            }
            System.out.println("compare1:" + compare1);
            System.out.println("compare2:" + compare2);
            System.out.println("index1:" + index1);
            System.out.println("index2:" + index2);
            System.out.println("k:" + k);


        }

    }


}

Note: while statement is the core part, which is the main idea of binary search.

Well, that's all for today. Thank you for coming here. Why don't you pay attention!