LeetCode #4 Median of Two Sorted Arrays


1. 題目(Problem Statement)

  • 英文

    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)).

  • 中文

    給定兩個已排序的陣列 nums1 和 nums2,大小分別為 m 和 n,請返回這兩個已排序陣列的中位數。整體運行時間複雜度應為 O(log (m+n))。

2. 題目說明與解決方案(Explanation and Solution)

這道題目要求我們找到兩個已排序陣列的中位數。中位數是一組數字中間的值,對於偶數個數字的集合,中位數是中間兩個數字的平均值。

解決這個問題的最佳方法是使用二分搜尋法來合併兩個陣列,同時保持整體運行時間複雜度為 O(log (m+n))。用一種方法來分割兩個陣列,使得左邊部分的元素總數等於右邊部分的元素總數。

但要達到時間複雜度為 O(log (m+n))確實很不容易。我自己是用一種簡單的方法,將兩個陣列合併並排序,然後根據合併後的陣列來計算中位數。這種方法的運行時間複雜度為 O((m+n) log (m+n)),雖然不符合最佳要求,但其邏輯簡單易於實現。(放棄思考XDDD)

3. 範例(Example)

1Example 1:
2    Input: nums1 = [1,3], nums2 = [2]
3    Output: 2.00000
4---
5Example 2:
6    Input: nums1 = [1,2], nums2 = [3,4]
7    Output: 2.50000

4. 限制條件(Constraints)

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • 10^6 <= nums1[i], nums2[i] <= 10^6

5. C# 解法(C# Solution)

 1using System;
 2using System.Linq;
 3
 4namespace LeetCode
 5{
 6    public class Solution
 7    {
 8        public double FindMedianSortedArrays(int[] nums1, int[] nums2)
 9        {
10            var mergedArray = nums1.Concat(nums2).ToArray();
11            Array.Sort(mergedArray);
12            var length = mergedArray.Length;
13            if (length % 2 == 0)
14                return (mergedArray[length / 2 - 1] + mergedArray[length / 2]) / 2.0;
15            else
16                return mergedArray[length / 2];
17        }
18    }
19}

6. C# 程式碼說明(C# Code Explanation)

這段程式碼的主要步驟如下:

  1. 使用 Concat 方法將兩個陣列合併成一個陣列。

  2. 使用 Array.Sort 方法對合併後的陣列進行排序。

  3. 計算合併後陣列的長度,判斷長度是否為偶數:

    • 如果是偶數,返回中間兩個元素的平均值。
    • 如果是奇數,返回中間元素。

7. C# 單元測試(C# Unit Tests)

 1using System;
 2using Microsoft.VisualStudio.TestTools.UnitTesting;
 3
 4namespace LeetCode.Tests
 5{
 6    [TestClass]
 7    public class SolutionTests
 8    {
 9        [TestMethod]
10        public void TestCase1()
11        {
12            var solution = new Solution();
13            int[] nums1 = {1, 3};
14            int[] nums2 = {2};
15            double result = solution.FindMedianSortedArrays(nums1, nums2);
16            Assert.AreEqual(2.0, result);
17        }
18
19        [TestMethod]
20        public void TestCase2()
21        {
22            var solution = new Solution();
23            int[] nums1 = {1, 2};
24            int[] nums2 = {3, 4};
25            double result = solution.FindMedianSortedArrays(nums1, nums2);
26            Assert.AreEqual(2.5, result);
27        }
28
29        [TestMethod]
30        public void TestCase3()
31        {
32            var solution = new Solution();
33            int[] nums1 = {0, 0};
34            int[] nums2 = {0, 0};
35            double result = solution.FindMedianSortedArrays(nums1, nums2);
36            Assert.AreEqual(0.0, result);
37        }
38    }
39}

8. Python 解法(Python Solution)

1class Solution:
2    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
3        merged_array = sorted(nums1 + nums2)
4        length = len(merged_array)
5        if length % 2 == 0:
6            return (merged_array[length // 2 - 1] + merged_array[length // 2]) / 2.0
7        else:
8            return merged_array[length // 2]

9. Python 程式碼說明(Python Code Explanation)

這段 Python 程式碼的主要步驟如下:

  1. 使用 + 運算符將兩個陣列合併成一個陣列。

  2. 使用 sorted 函數對合併後的陣列進行排序。

  3. 計算合併後陣列的長度,判斷長度是否為偶數:

    • 如果是偶數,返回中間兩個元素的平均值。
    • 如果是奇數,返回中間元素。

10. Python 單元測試(Python Unit Tests)

 1import unittest
 2
 3class TestSolution(unittest.TestCase):
 4    def test_case_1(self):
 5        solution = Solution()
 6        nums1 = [1, 3]
 7        nums2 = [2]
 8        result = solution.findMedianSortedArrays(nums1, nums2)
 9        self.assertEqual(result, 2.0)
10
11    def test_case_2(self):
12        solution = Solution()
13        nums1 = [1, 2]
14        nums2 = [3, 4]
15        result = solution.findMedianSortedArrays(nums1, nums2)
16        self.assertEqual(result, 2.5)
17
18    def test_case_3(self):
19        solution = Solution()
20        nums1 = [0, 0]
21        nums2 = [0, 0]
22        result = solution.findMedianSortedArrays(nums1, nums2)
23        self.assertEqual(result, 0.0)
24
25if __name__ == '__main__':
26    unittest.main()

11. 總結(Summary)

這道題目要求我們在兩個已排序陣列中找到中位數。我們使用了將兩個陣列合併並排序的方法,然後根據合併後的陣列來計算中位數。這種方法簡單直接,但運行時間複雜度為 O((m+n) log (m+n)),在數據量較小的情況下仍然是可行的解決方案。

時間複雜度:O((m+n) log (m+n))

空間複雜度:O(m+n)


這邊必須補充說明一下,使用了二分搜尋法來實現這一目標,使得整體運行時間複雜度為 O(log (m+n))。這樣的解法效率高,且在處理大數據集時表現優異。

時間複雜度:O(log (m+n))

空間複雜度:O(1)

有參考一下大師們的寫法,需要花點時間理解,也放上來給大家參考啦Q_Q

 1using System;
 2
 3namespace LeetCode
 4{
 5    public class Solution
 6    {
 7        public double FindMedianSortedArrays(int[] nums1, int[] nums2)
 8        {
 9            int m = nums1.Length;
10            int n = nums2.Length;
11            if (m > n)
12            {
13                int[] temp = nums1; nums1 = nums2; nums2 = temp;
14                int tmp = m; m = n; n = tmp;
15            }
16            int imin = 0, imax = m, halfLen = (m + n + 1) / 2;
17            while (imin <= imax)
18            {
19                int i = (imin + imax) / 2;
20                int j = halfLen - i;
21                if (i < m && nums2[j-1] > nums1[i])
22                {
23                    imin = i + 1;
24                }
25                else if (i > 0 && nums1[i-1] > nums2[j])
26                {
27                    imax = i - 1;
28                }
29                else
30                {
31                    int maxOfLeft;
32                    if (i == 0) { maxOfLeft = nums2[j-1]; }
33                    else if (j == 0) { maxOfLeft = nums1[i-1]; }
34                    else { maxOfLeft = Math.Max(nums1[i-1], nums2[j-1]); }
35                    if ((m + n) % 2 == 1) { return maxOfLeft; }
36
37                    int minOfRight;
38                    if (i == m) { minOfRight = nums2[j]; }
39                    else if (j == n) { minOfRight = nums1[i]; }
40                    else { minOfRight = Math.Min(nums1[i], nums2[j]); }
41
42                    return (maxOfLeft + minOfRight) / 2.0;
43                }
44            }
45            return 0.0;
46        }
47    }
48}

這段程式碼使用二分搜尋法來合併兩個已排序陣列,並找到中位數。程式碼的主要步驟如下:

  1. 確保 nums1 的長度不大於 nums2,如果不滿足則交換兩個陣列。

  2. 設定 imin 和 imax 為搜尋範圍的起始和結束位置。

  3. 使用 while 迴圈執行二分搜尋:

    • 計算 i 和 j,i 是 nums1 的分割點,j 是 nums2 的分割點。

    • 檢查分割是否正確:

      • 如果 nums1[i] 小於 nums2[j-1],則需要增加 i。
      • 如果 nums1[i-1] 大於 nums2[j],則需要減少 i。
  4. 當找到正確的分割點時,計算左邊和右邊的最大值和最小值,並返回中位數。

comments powered by Disqus
>