寻找两个正序数组的中位数

题目

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

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

1
2
3
4
5
6
7
8
9
10
示例 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

提示

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

代码

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * Author: Rupert Tears
 * Date: Created in 0:32 2022/11/5
 * Description: Thought is already is late, exactly is the earliest time.
 * 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * <p>
 * 解题思路：将数组进行合并，根据长度情况取中位数
 * 如何在数组中插入元素
 * <p>
 * 数组中存放的都为正整数时：以下算法满足
 */
public class Aigo_004 {


    public static void main(String[] args) {

        int[] nums1 = {1, 2, 3};
        int[] nums2 = {1, 2};

        double result = findMedianSortedArrays(nums1, nums2);

        System.out.println(result);


    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {


        List<String> arr1 = new ArrayList<>();
        List<String> arr2 = new ArrayList<>();


        for (int k : nums1) {
            arr1.add(String.valueOf(k));
        }


        for (int k : nums2) {
            arr2.add(String.valueOf(k));
        }


        System.out.println("arr1:" + arr1);
        System.out.println("arr2:" + arr2);

        int len1 = arr1.size();
        int len2 = arr2.size();

        if (len1 == 0 && len2 != 0) {
            int resLength = arr2.size();
            if (resLength % 2 == 0) {
                String res1 = arr2.get((resLength / 2) - 1);
                String res2 = arr2.get((resLength / 2));
                int v1 = Integer.parseInt(res1);
                int v2 = Integer.parseInt(res2);
                double sum = (v1 + v2);
                double res = sum / 2;
                System.out.println(res);
                return res;
            } else {
                String res1 = arr2.get((resLength / 2));
                int res = Integer.parseInt(res1);
                System.out.println(res);
                return res;
            }
        }

        if (len1 != 0 && len2 == 0) {
            int resLength = arr1.size();
            if (resLength % 2 == 0) {
                String res1 = arr1.get((resLength / 2) - 1);
                String res2 = arr1.get((resLength / 2));
                int v1 = Integer.parseInt(res1);
                int v2 = Integer.parseInt(res2);
                double sum = (v1 + v2);
                double res = sum / 2;
                System.out.println(res);
                return res;
            } else {
                String res1 = arr1.get((resLength / 2));
                int res = Integer.parseInt(res1);
                System.out.println(res);
                return res;
            }
        }


        if (len2 >= len1) {
            // nums1 次插入数据
            for (String s : arr1) {     // len1 插入
                // nums1 中的每一个数字和 插入数字比对
                for (int j = 0; j < arr2.size(); j++) {     // 最多4次比对
                    // 如果相等
                    if (arr2.get(j).equals(s)) {
                        arr2.add(j, s);
                        break;
                    }
                    // 若小于目标值
                    else if (Integer.parseInt(arr2.get(j)) > Integer.parseInt(s)) {
                        arr2.add(j, s);
                        break;
                    } else {
                        if (j == arr2.size() - 1) {
                            arr2.add(j + 1, s);
                            break;
                        }
                    }

                }
            }
            System.out.println(arr2);
            int resLength = arr2.size();
            if (resLength % 2 == 0) {
                String res1 = arr2.get((resLength / 2) - 1);
                String res2 = arr2.get((resLength / 2));
                int v1 = Integer.parseInt(res1);
                int v2 = Integer.parseInt(res2);
                double sum = (v1 + v2);
                double res = sum / 2;
                System.out.println(res);
                return res;
            } else {
                String res1 = arr2.get((resLength / 2));
                int res = Integer.parseInt(res1);
                System.out.println(res);
                return res;
            }
        }

        // 2向1插入数据
        for (String s : arr2) {
            // 与1中的逐一比对
            for (int j = 0; j < arr1.size(); j++) {
                // 如果相等
                if (s.equals(arr1.get(j))) {
                    arr1.add(j, s);
                    break;
                }
                // 如果小于
                else if (Integer.parseInt(s) < Integer.parseInt(arr1.get(j))) {
                    arr1.add(j, s);
                    break;
                } else {
                    if (j == arr1.size() - 1) {
                        arr1.add(s);
                        break;
                    }
                }

            }
        }
        System.out.println(arr1);
        int resLength = arr1.size();
        if (resLength % 2 == 0) {
            String res1 = arr1.get((resLength / 2) - 1);
            String res2 = arr1.get((resLength / 2));
            int v1 = Integer.parseInt(res1);
            int v2 = Integer.parseInt(res2);
            double sum = (v1 + v2);
            double res = sum / 2;
            System.out.println(res);
            return res;

        } else {
            String res1 = arr1.get((resLength / 2));
            int res = Integer.parseInt(res1);
            System.out.println(res);
            return res;

        }
    }
}