LeetCode Median of Two Sorted Arrays

看到Hard就來看看

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

直覺寫法
public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
                var merged = nums1.Concat(nums2);

        var mergedArray = merged.OrderBy(a => a).ToArray();
        
        if (mergedArray.Length % 2 > 0)
        {
            var median = mergedArray[(mergedArray.Length - 1) / 2];
            return median;
        }
        else
        {
            var medianFirst = mergedArray[((mergedArray.Length) / 2)-1];
            var medianLast = mergedArray[((mergedArray.Length) / 2)];
            return ((double)medianFirst + (double)medianLast) / 2;
        }
    }
}

結果就這樣過了，到底為什麼是Hard？

看了某些人也是這樣寫
Complexity:
Time complexity: The time complexity is dominated by the sorting operation, which takes O(N log N) time, where N is the total number of elements in nums1 and nums2.
Space complexity: The space complexity is determined by the size of the combined list nums, which is O(N), where N is the total number of elements in nums1 and nums2.

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
         List<int> nums = nums1.ToList();
            nums.AddRange(nums2.ToList());
            nums.Sort();
            if(nums.Count % 2 == 1)
                return nums[nums.Count/2];

            return (nums[nums.Count/2] + nums[nums.Count/2 - 1])/2.0;
    }
}

所以這題的難度感覺是如何 說明其時間複雜度吧XD