-
Notifications
You must be signed in to change notification settings - Fork 0
/
q4_find_median_sorted_arrays.rs
70 lines (57 loc) · 1.81 KB
/
q4_find_median_sorted_arrays.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*!
[4. Median of Two Sorted Arrays](https://leetcode.com/problems/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:
```html
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
```
Example 2:
```html
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
```
*/
fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
let length = nums1.len() + nums2.len();
let (mut temp, mut index1, mut index2) = (vec![], 0, 0);
let mut deal_value = |v: &i32, index: &mut usize| {
temp.push(*v);
*index += 1;
};
loop {
// put the elements which in nums1 or nums2 into new Vec
match (nums1.get(index1), nums2.get(index2)) {
(Some(v1), Some(v2)) if v1 < v2 => deal_value(v1, &mut index1),
(Some(v), None) => deal_value(v, &mut index1),
(_, Some(v)) => deal_value(v, &mut index2),
_ => {
// check whether the length is odd or even, then compute the median
break if length % 2 == 0 {
(temp[length / 2 - 1] + temp[length / 2]) as f64 / 2_f64
} else {
temp[length / 2] as f64
};
}
}
}
}
#[test]
fn q4_test() {
assert_eq!(find_median_sorted_arrays(vec![], vec![1]), 1.0);
assert_eq!(find_median_sorted_arrays(vec![1, 3], vec![2]), 2.0);
assert_eq!(find_median_sorted_arrays(vec![1, 2], vec![2, 4]), 2.0);
assert_eq!(find_median_sorted_arrays(vec![], vec![2, 21, 20, 30]), 20.5);
assert_eq!(
find_median_sorted_arrays(vec![1, 3, 6, 7, 8, 10, 20, 20, 20, 20], vec![]),
9.0
);
assert_eq!(
find_median_sorted_arrays(vec![1, 3, 6, 7, 8, 10, 20, 20, 20, 20], vec![2, 20, 20, 30]),
15.0
);
}