LeetCode 4: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)).

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

 

初看这题,超简单的样子,两个已经排好序的数组,返回合并之后数组的中位数,思路比较清晰,写写看

package com.maoxiaomeng;

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

/**
* @author lihui
* @date 2018/3/25 15:23
*/
public class Solution {

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
List<Integer> myList = new ArrayList<Integer>();
for (int num : nums1) {
myList.add(num);
}
for (int num: nums2) {
myList.add(num);
}
Collections.sort(myList);

int len1 = nums1.length;
int len2 = nums2.length;
int len = len1 + len2;
double temp = 0.0;
if (len % 2 == 0) {
temp = (myList.get(len / 2) + myList.get(len / 2 - 1)) / 2.0;
} else {
temp = myList.get((len - 1) / 2);
}

return temp;
}
}

定义一个泛型ArrayList,将两个数组的值添加进去,然后从小到大进行一个排序,因为并不是一个数组都比另一个数组的值大,排序好按奇偶返回即可

提交了下,直接就通过了,这就有点奇怪了,还是个Hard难度的,但是好像的确有个问题,要求复杂度O(log (m+n)),这好像二分查找的复杂度,这里有问题

发表回复