NoteOfCode/midnumber.java at main · ruiizhi792/NoteOfCode · GitHub

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

    /*给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。


示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5


来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length, medium = 0;
        if ((m + n) % 2 == 0) {
            medium = (m + n) / 2 - 1;
        } else if ((m + n) % 2 != 0){
            medium = (m + n) / 2;
        }
        int index1 = 0, index2 = 0;
        if (m == 0 && n == 0) {
            return 0;
        } else if (m == 0 && n != 0) {
            if (n % 2 == 0) {
                return (double)(nums2[medium] + nums2[medium + 1]) / 2;
            } else if (n % 2 != 0) {
                return nums2[medium];
            }
        } else if (m != 0 && n == 0) {
            if (m % 2 == 0) {
                return (double)(nums1[medium] + nums1[medium + 1]) / 2;
            } else if (m % 2 != 0) {
                return nums1[medium];
            }
        }
        int count = 0, next = 0;
        while (index1 < m && index2 < n) {
            if (nums1[index1] < nums2[index2]) {
                if (count == medium) {
                    if ((m + n) % 2 == 0) {
                        if (index1 == m - 1){
                            next = nums2[index2];
                        } else {
                            next = Math.min(nums1[index1 + 1], nums2[index2]);
                        }
                        return (double)(nums1[index1] + next) / 2;
                    } else if ((m + n) % 2 != 0) {
                        return nums1[index1];
                    }
                }
                if (index1 != m - 1) {
                    ++index1;
                    ++count;
                }
                else {
                    if ((m + n) % 2 == 0) {
                        return (double)(nums2[medium - m] + nums2[medium - m + 1]) / 2;
                    } else if ((m + n) % 2 != 0) {
                        return nums2[medium - m];
                    }
                }
            } else if (nums1[index1] > nums2[index2]){
                if (count == medium) {
                    if ((m + n) % 2 == 0) {
                        if (index2 == n - 1){
                            next = nums1[index1];
                        } else {
                            next = Math.min(nums1[index1], nums2[index2 + 1]);
                        }
                        return (double)(nums2[index2] + next) / 2;
                    } else if ((m + n) % 2 != 0) {
                        return nums2[index2];
                    }
                }
                if (index2 != n - 1) {
                    ++index2;
                    ++count;
                } else {
                    if ((m + n) % 2 == 0) {
                        return (double)(nums1[medium - n] + nums1[medium - n + 1]) / 2;
                    } else if ((m + n) % 2 != 0) {
                        return nums1[medium - n];
                    }
                }
            } else {
                if (count == medium) {
                    if ((m + n) % 2 == 0) {
                        if (index1 == m - 1){
                            next = nums2[index2];
                        } else {
                            next = Math.min(nums1[index1 + 1], nums2[index2]);
                        }
                        return (double)(nums1[index1] + next) / 2;
                    } else if ((m + n) % 2 != 0) {
                        return nums1[index1];
                    }
                }
                if (index1 != m - 1) {
                    ++index1;
                    ++count;
                }
                else {
                    if ((m + n) % 2 == 0) {
                        return (double)(nums2[medium - m] + nums2[medium - m + 1]) / 2;
                    } else if ((m + n) % 2 != 0) {
                        return nums2[medium - m];
                    }
                }
                if (count == medium) {
                    if ((m + n) % 2 == 0) {
                        if (index2 == n - 1){
                            next = nums1[index1];
                        } else {
                            next = Math.min(nums1[index1], nums2[index2 + 1]);
                        }
                        return (double)(nums2[index2] + next) / 2;
                    } else if ((m + n) % 2 != 0) {
                        return nums2[index2];
                    }
                }
                if (index2 != n - 1) {
                    ++index2;
                    ++count;
                } else {
                    if ((m + n) % 2 == 0) {
                        return (double)(nums1[medium - n] + nums1[medium - n + 1]) / 2;
                    } else if ((m + n) % 2 != 0) {
                        return nums1[medium - n];
                    }
                }
            }
        }
        return 0;
    }
}