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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
use super::Solution;
impl Solution {
pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
let (len_a, len_b) = (nums1.len(), nums2.len());
let (a, len_a, b, len_b) = if len_a <= len_b {
(nums1, len_a, nums2, len_b)
} else {
(nums2, len_b, nums1, len_a)
};
let index_sum = (a.len() + b.len() + 1) / 2;
let (mut i_min, mut i_max) = (0, len_a);
while i_min != i_max {
let i = (i_min + i_max) / 2;
let j = index_sum - i;
if j != 0 && a[i] < b[j - 1] {
i_min = i + 1;
} else {
i_max = i;
}
}
let i = i_min;
let j = index_sum - i;
let mut v = vec![];
if i != 0 {
v.push(a[i - 1]);
}
if j != 0 {
v.push(b[j - 1]);
}
if i != len_a {
v.push(a[i]);
}
if j != len_b {
v.push(b[j]);
}
v.sort_unstable();
println!("{:?}", v);
if (len_a + len_b) % 2 == 0 {
match v.len() {
2 => (v[0] as f64 + v[1] as f64) / 2.0,
3 => {
if i == 0 {
(v[0] as f64 + v[1] as f64) / 2.0
} else {
(v[1] as f64 + v[2] as f64) / 2.0
}
}
4 => (v[1] as f64 + v[2] as f64) / 2.0,
_ => panic!(),
}
} else {
match v.len() {
1 | 2 => v[0] as f64,
3 => {
if i == 0 {
v[0] as f64
} else {
v[1] as f64
}
}
4 => v[1] as f64,
_ => panic!(),
}
}
}
}
#[cfg(test)]
mod tests {
use super::Solution;
#[test]
fn test() {
assert_eq!(Solution::find_median_sorted_arrays(vec![3], vec![]), 3.0);
assert_eq!(Solution::find_median_sorted_arrays(vec![3], vec![4]), 3.5);
assert_eq!(
Solution::find_median_sorted_arrays(vec![3, 4, 5], vec![1, 2, 6]),
3.5
);
assert_eq!(
Solution::find_median_sorted_arrays(vec![3, 4], vec![1, 2, 6]),
3.0
);
assert_eq!(
Solution::find_median_sorted_arrays(vec![1], vec![2, 3, 4]),
2.5
);
assert_eq!(
Solution::find_median_sorted_arrays(vec![4], vec![1, 2, 3, 5]),
3.0
);
assert_eq!(
Solution::find_median_sorted_arrays(vec![1, 2, 3], vec![4, 5, 6]),
3.5
);
}
}
|
