代码拉取完成,页面将自动刷新
package pers.vic.basics.leetcode;
import java.util.Arrays;
/**
* @author Vic.xu
* @description:4. 寻找两个正序数组的中位数
* 给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
* <p>
* 进阶:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗?
* @date: 2020/10/29 11:00
*/
public class J0004_H_FindMedianSortedArrays {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
//求出中间数
int len1 = nums1.length;
int len2 = nums2.length;
int len = len1 + len2;
//两个数组合起来的长度是不是偶数
boolean isEven = len % 2 == 0;
int left = 0;
int right = 0;
if (isEven) {
right = len / 2;
left = right - 1;
} else {
right = left = len / 2;
}
int[] midArr = new int[2];
int i = 0, j = 0, k = 0;
while (k <= right) {
int val = 0;
boolean arriveLeft = k == left;
boolean arriveRight = k == right;
if (i < len1 && j < len2) {
if (nums1[i] < nums2[j]) {
val = nums1[i];
i++;
} else {
val = nums2[j];
j++;
}
} else if (i < len1 && j >= len2) {
val = nums1[i];
i++;
} else if (j < len2 && i >= len1) {
val = nums2[j];
j++;
}
if (arriveLeft) {
midArr[0] = val;
}
if (arriveRight) {
midArr[1] = val;
break;
}
k++;
}
return (midArr[0] + midArr[1]) / 2.0;
}
public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
int[] arr = mergeOrderedArrays(nums1, nums2);
int len = arr.length;
if (len % 2 == 0) {
return (arr[len / 2] + arr[len / 2 - 1]) / 2.000000;
} else {
return arr[len / 2] / 1.000000;
}
}
public static int[] mergeOrderedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int len = len1 + len2;
int[] arr = new int[len];
int i = 0, j = 0, k = 0;
while (k < len) {
if (i < len1 && j < len2) {
if (nums1[i] < nums2[j]) {
arr[k++] = nums1[i++];
} else {
arr[k++] = nums2[j++];
}
} else if (i < len1 && j >= len2) {
arr[k++] = nums1[i++];
} else if (j < len2 && i >= len1) {
arr[k++] = nums2[j++];
}
}
return arr;
}
public static void main(String[] args) {
System.out.println("123");
int[] arr1 = {1, 3};
int[] arr2 = {2};
int[] arr = mergeOrderedArrays(arr1, arr2);
System.out.println(Arrays.toString(arr));
System.out.println(findMedianSortedArrays2(arr1, arr2));
System.out.println(findMedianSortedArrays(arr1, arr2));
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。