英文:
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))。
這道題目要求我們找到兩個已排序陣列的中位數。中位數是一組數字中間的值,對於偶數個數字的集合,中位數是中間兩個數字的平均值。
解決這個問題的最佳方法是使用二分搜尋法來合併兩個陣列,同時保持整體運行時間複雜度為 O(log (m+n))。用一種方法來分割兩個陣列,使得左邊部分的元素總數等於右邊部分的元素總數。
但要達到時間複雜度為 O(log (m+n))確實很不容易。我自己是用一種簡單的方法,將兩個陣列合併並排序,然後根據合併後的陣列來計算中位數。這種方法的運行時間複雜度為 O((m+n) log (m+n)),雖然不符合最佳要求,但其邏輯簡單易於實現。(放棄思考XDDD)
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
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}
這段程式碼的主要步驟如下:
使用 Concat
方法將兩個陣列合併成一個陣列。
使用 Array.Sort
方法對合併後的陣列進行排序。
計算合併後陣列的長度,判斷長度是否為偶數:
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}
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]
這段 Python 程式碼的主要步驟如下:
使用 +
運算符將兩個陣列合併成一個陣列。
使用 sorted
函數對合併後的陣列進行排序。
計算合併後陣列的長度,判斷長度是否為偶數:
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()
這道題目要求我們在兩個已排序陣列中找到中位數。我們使用了將兩個陣列合併並排序的方法,然後根據合併後的陣列來計算中位數。這種方法簡單直接,但運行時間複雜度為 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}
這段程式碼使用二分搜尋法來合併兩個已排序陣列,並找到中位數。程式碼的主要步驟如下:
確保 nums1 的長度不大於 nums2,如果不滿足則交換兩個陣列。
設定 imin 和 imax 為搜尋範圍的起始和結束位置。
使用 while 迴圈執行二分搜尋:
計算 i 和 j,i 是 nums1 的分割點,j 是 nums2 的分割點。
檢查分割是否正確:
當找到正確的分割點時,計算左邊和右邊的最大值和最小值,並返回中位數。