LeetCode算法题解-第四道题
阅读“关于 7 分钟
Hi! 
LeetCode 第四道题: Median of Two Sorted Arrays，难度困难。
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3] nums2 = [2]
The median is 2.0 Example 2:
nums1 = [1, 2] nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
###第一种解法，算法复杂度不满足要求
1 public class Solution {
2 public double FindMedianSortedArrays(int[] nums1, int[] nums2)
3 {
4
5 var i = 0;
6 var j = 0;
7
8 var num = new List<int>();
9 while (i < nums1.Length && j < nums2.Length)
10 {
11 if (nums1[i] < nums2[j])
12 {
13 num.Add(nums1[i]);
14 i++;
15 }
16 else
17 {
18 num.Add(nums2[j]);
19 j++;
20 }
21 }
22
23 while (i < nums1.Length )
24 {
25 num.Add(nums1[i]);
26 i++;
27 }
28
29 while (j < nums2.Length )
30 {
31 num.Add(nums2[j]);
32 j++;
33 }
34
35 if (num.Count == 0)
36 {
37 return 0;
38 }
39 if (num.Count % 2 == 0)
40 {
41 return (num[num.Count / 2] + num[num.Count / 2 - 1]) / 2f;
42 }
43 else
44 {
45 return num[num.Count / 2];
46 }
47
48 return 0;
49 }
50 }第二种解法，示例解法：
1 public class Solution {
2 public double FindMedianSortedArrays(int[] nums1, int[] nums2)
3 {
4
5 var m = nums1.Length;
6 var n = nums2.Length;
7 if (m > n)
8 {
9 var temp = m;
10 m = n;
11 n = temp;
12
13 var tempArr = nums1;
14 nums1 = nums2;
15 nums2 = tempArr;
16 }
17
18 var low = 0;
19 var high = m;
20 var half = (m + n + 1) / 2;
21
22 while (low <= high)
23 {
24 var i = (low + high) / 2;
25 var j = half - i;
26
27 if (i > low && nums1[i-1] > nums2[j])
28 {
29 high = i - 1;
30 }
31 else if (i < high && nums2[j - 1] > nums1[i])
32 {
33 low = i + 1;
34 }
35 else
36 {
37 int maxLeft = 0;
38 if (i == 0)
39 {
40 maxLeft = nums2[j - 1];
41
42 }
43 else if (j == 0)
44 {
45 maxLeft = nums1[i - 1];
46 }
47 else
48 {
49 maxLeft = Math.Max(nums1[i - 1], nums2[j - 1]);
50 }
51
52 if ((m + n) % 2 == 1)
53 {
54 return maxLeft;
55 }
56
57 int minRight = 0;
58 if ( i == m)
59 {
60 minRight = nums2[j];
61 }
62 else if (j == n)
63 {
64 minRight = nums1[i];
65 }
66 else
67 {
68 minRight = Math.Min(nums1[i], nums2[j]);
69 }
70
71 return (maxLeft + minRight) / 2f;
72 }
73 }
74
75 return 0f;
76 }
77 }Gist code
To use, see:Jektify - Doc
- jektify © 2019
-
Música
Goodbye! 
The word of the day!
Put a very powerful message.