leetcode刷题记-004
2019-03-08 / 2 min read
问题
解题思路
思路一， 借鉴有序链表合并的思路
虽然leetcode标记为困难。但实际上很容易会想到“有序链表合并”的思路，在这个思路的基础之上记录下来中间值位置。对于中间值位置，由于在两个数组的长度之和是偶数的时候，需要取中间前后的两个数值计算中间值，所以需要记录前后两个值。附代码：
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int totalLength = nums1.length + nums2.length;
boolean oddFlag = totalLength % 2 == 1;
final int middleVal = oddFlag ? totalLength / 2 + 1 : totalLength / 2 + 1;
//navigate likes two linklists merging
int countIndex = 1, idx1 = 0, idx2 = 0;
int midPrev = 0, current = 0;
while (true) {
midPrev = current;
if (idx1 < nums1.length && idx2 < nums2.length) {
if (nums1[idx1] <= nums2[idx2]) {
current = nums1[idx1];
idx1++;
} else {
current = nums2[idx2];
idx2++;
}
} else if (idx1 >= nums1.length) {
current = nums2[idx2];
idx2++;
} else {
current = nums1[idx1];
idx1++;
}
if (countIndex == middleVal) {
return oddFlag ? current : (midPrev + current) / 2.0;
}
countIndex++;
}
}
这里需要说明的是midPrev记录前值，current记录当前值，总长是奇数长度的只需要关注current即可，否则需要用于加和求中间值，也就是return oddFlag ? current : (midPrev + current) / 2.0
Runtime: 24 ms, faster than 94.52% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 49 MB, less than 58.57% of Java online submissions for Median of Two Sorted Arrays.
不幸的是，这个答案是错的！时间复杂度是O(m+n), 而不是O(log(m+n))。LeetCode居然没能够检测出来。