“These are the 4 days I participated in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

preface

I have been planning to learn data structures and basic algorithms, but I have seen them in fits and starts. Now I’m determined to stick to it. I’m going to start with LeetCode’s HOT100 and finish 1~2 exercises every day, hoping to develop the habit of continuous learning in this way. Because I am doing iOS development, mainly using Objective-C language, and I am also learning Swift recently, all the questions in this series will be solved using Swift language. The updated question in this paper is question 004 of HOT100 in LeetCode, finding the median of two positive ordinal groups.

The title

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. Example 1:

Input: nums1 = [1,3], nums2 = [2] output: 2.00000 explanation: merge array = [1,2,3], median 2Copy the code

Example 2:

Input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5Copy the code

Example 3:

Input: nums1 = [0,0], nums2 = [0,0] output: 0.00000Copy the code

Example 4:

Input: nums1 = [], nums2 = [1] Output: 1.00000Copy the code

Example 5:

Input: nums1 = [2], nums2 = [] Output: 2.00000Copy the code

Analysis of the

If the number of elements in the array is odd, there is only one median. If the number of elements in the array is even, there are two medians. Take the average of the two medians. So, the easy way is to combine two ordered arrays into one ordered array, and then find the median based on the odd and even of the total number. The solution of this paper is achieved through this method, but this paper does not merge the two arrays completely, only merge the half of the array, and then directly take the data in the middle to calculate.

Answer key

class KLLC004 {
    func findMedianSortedArrays(_ nums1: [Int]._ nums2: [Int]) -> Double {
        let totalCount = nums1.count + nums2.count
        // Both arrays are empty
        if totalCount = = 0 {
            return -1.0
        }
        // Merge record arrays
        var mergeArr = Array<Int>(repeating: 0, count: totalCount)
        // The index of the corresponding array during the merge
        var index1 = 0, index2 = 0, index0 = 0
        while index1 < nums1.count || index2 < nums2.count {
            // Merge all numbers in array 1 less than the current value of index2 in array 2
            while index1 < nums1.count && (index2 = = nums2.count || nums2[index2] > = nums1[index1]) {
                mergeArr[index0] = nums1[index1]
                index0 + = 1
                index1 + = 1
            }
            // Merge all numbers in array 2 less than the current value of index1 in array 1
            while index2 < nums2.count && (index1 = = nums1.count || nums1[index1] > = nums2[index2]) {
                mergeArr[index0] = nums2[index2]
                index0 + = 1
                index2 + = 1
            }
            // If more than half of the data is merged, the processing ends
            if index0 > totalCount/2 {
                break}}// Calculate the median according to the parity of the total number
        if totalCount % 2 = = 0 {
            return Double(mergeArr[totalCount/2 - 1] + mergeArr[totalCount/2])/2
        } else {
            return Double(mergeArr[totalCount/2])}}}Copy the code