给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
上中位数：假设递增序列长度为n，为第n/2个数
数据范围：
， 
要求：时间复杂度 )
，空间复杂度 )
进阶：时间复杂度为)
，空间复杂度为
[编程题]在两个长度相等的排序数组中找到上中位数
举个例子：
arr1：1,2,8,9
arr2：3,4,5,6
这里两个数组的长度均为4，
第一步：(3+0)/2=1，所以比较2和4，
1, 2, 8,9
3, 4, 5,6
由于2<4，所以结果一定在如下两个子集，那么下一步判断这两个子集，
1,2, 8,9
3,4, 5,6
对于arr1，(3+2)/2=2，对于arr2，(0+1)/2=0，所以判断8和3
1,2, 8, 9
3, 4, 5,6
由于3小于8，所以仍需判断：
1,2, 8, 9
3, 4, 5,6
此时只需返回较小值4即可。
判断条件为两个元素相等或只剩下一个元素。
代码如下：
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
if(arr1.size()==0 || arr2.size()==0)
return -1;
return recurseFindMedian(arr1, arr2, 0, arr1.size()-1, 0, arr2.size()-1);
}
int recurseFindMedian(vector<int>& arr1, vector<int>& arr2, int s1, int e1, int s2, int e2) {
if(s1==e1 && s2==e2)
return min(arr1[s1], arr2[s2]);
int mid1 = (e1+s1)/2;
int mid2 = (e2+s2)/2;
if(arr1[mid1] == arr2[mid2])
return arr1[mid1];
return arr1[mid1] < arr2[mid2] ?
recurseFindMedian(arr1, arr2, e1-mid2+s2, e1, s2, mid2) :
recurseFindMedian(arr1, arr2, s1, mid1, e2-mid1+s1, e2);
}
编辑于 2021-04-09 12:56:06
回复(1)
public static int findMedianinTwoSortedAray(int[] nums1, int[] nums2) {
/**
* 设nums1长度为m，nums2长度为n，设m <= n
* 将nums1与nums2分别进行分组，设nums1的左边长度为i，则右边长度 m - i；设nums2的左边长度为j，则右边长度为 n - j
* 如果m + n 为偶数，则有 i + j = m - i + n - j，如果 m + n 是奇数，则有 i + j = m - i + n - j + 1
* 因此有 j = （m + n + 1）/2 - i，（因为只取商，所以 m + n 的和无论是偶数还是奇数都满足这个结果）
* 还有 nums1[i - 1] <= nums2[j] 且 nums1[i] >= nums2[j - 1]
*
* 又因为 i ∈ [0, m]，如果需要同时满足条件（ nums1[i - 1] <= nums2[j] 且 nums1[i] >= nums2[j - 1]）
* 所以可以取最大的 i 使其满足nums1[i - 1] <= nums2[j]即可
*
*/
if (nums1.length > nums2.length) {
return findMedianinTwoSortedAray(nums2, nums1);
}
int len1 = nums1.length;
int len2 = nums2.length;
int start = 0;
int end = len1;
int median1 = 0;
while (start <= end) {
int mid = (start + end) / 2;
int nums2Index = (len1 + len2 + 1) / 2 - mid;
int nums1Left = mid == 0 ? Integer.MIN_VALUE : nums1[mid - 1];
int nums1Right = mid == len1 ? Integer.MAX_VALUE : nums1[mid];
int nums2Left = nums2Index == 0 ? Integer.MIN_VALUE : nums2[nums2Index - 1];
int nums2Right = nums2Index == len2 ? Integer.MAX_VALUE : nums2[nums2Index];
if (nums1Left <= nums2Right) {
median1 = Math.max(nums1Left, nums2Left);
start = mid + 1;
} else {
end = mid - 1;
}
}
return median1;
}
发表于 2021-01-07 17:00:38
回复(1)
class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
int n = arr1.size();
int left = 0, right = n-1; // binary search [0,n-1)
while(left < right) {
int m1 = left + ((right - left) >> 1); //
int m2 = n - m1 - 2;
if(arr1[m1] > arr2[m2+1]) {
right = m1;
}else if(arr2[m2] > arr1[m1+1]) {
left = m1 + 1;
}else if(arr1[m1] <= arr2[m2+1] && arr2[m2] <= arr1[m1+1]) {
return max(arr1[m1], arr2[m2]);
}
}
if(left == n-1) return arr1[n-1];
if(right == 0) return arr2[n-1];
}
}; 两个指针i, j 指向数组1第i个，数组2第j个。
i + j == n;
从第1个数组，[0, n-1)二分，若满足a[i]<= b[j+1] && b[j] <= a[i+1] 则ans = max(a[i], b[j])；
发表于 2020-10-23 03:45:22
回复(1)
class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
int m = arr1.size();
return getKmin(arr1, 0, m-1, arr2, 0, m-1, m);
}
int getKmin(vector<int>& nums1, int l1, int r1, vector<int>& nums2, int l2, int r2, int k){
int len1 = r1-l1+1;
int len2 = r2-l2+1;
if(len1 == 0){
return nums2[l2+k-1];
}
if(len2 == 0){
return nums1[l1+k-1];
}
if(k == 1){
return min(nums1[l1], nums2[l2]);
}
int nl1 = l1 + min(len1, k/2) - 1;
int nl2 = l2 + min(len2, k/2) - 1;
if(nums1[nl1] <= nums2[nl2]){
return getKmin(nums1, nl1+1, r1, nums2, l2, r2, k - (nl1-l1+1));
}
else{
return getKmin(nums1, l1, r1, nums2, nl2+1, r2, k - (nl2-l2+1));
}
}
};
发表于 2021-05-22 21:27:45
回复(0)
都说这道题是披着medium皮的hard，我稀里糊涂的过了，也不知道对不对，这里说下大概思路：2个排序数组取第n大的数
1. 数组1取 m1 个，数组2 取 m2 个数，则有 m1+m2 = n
2. m1 和 m2 通过二分求取。
满足答案的条件有三种情况（前提是 m1+m2 == n）：
1. arr1[m1] == arr2[m2] -> arr1[m1];
2. (arr1[m1] < arr2[m2]) && (m2 == 0 || (m2 > 0 && arr1[m1] >= arr2[m2-1])) -> arr1[m1];
3. (arr2[m2] < arr1[m1]) && (m1 == 0 || (m1 > 0 && arr2[m2] >= arr1[m1-1]))-> arr2[m2];
其他情况，则调整 m1,m2 的指，完整代码如下：
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
int n = arr1.size() - 1;
int l1 = 0,h1 = n,l2 = 0,h2 = n,m1,m2;
while(l1 <= h1 && l2 <= h2) {
m1 = (l1 + h1)/2;
m2 = (l2 + h2)/2;
if (m1 + m2 == n) {
if (arr1[m1] == arr2[m2]) return arr1[m1];
else if (arr1[m1] < arr2[m2]) {
if (m2 == 0 || (m2 > 0 && arr1[m1] >= arr2[m2-1])) return arr1[m1];
else l1 = m1 + 1;
}
else {
if (m1 == 0 || (m1 > 0 && arr2[m2] >= arr1[m1-1])) return arr2[m2];
else l2 = m2 + 1;
}
}
else if (m1 + m2 < n) {
if (arr1[m1] < arr2[m2]) l1 = m1 + 1;
else l2 = m2 + 1;
}
else {
if (arr1[m1] > arr2[m2]) h1 = m1 - 1;
else h2 = m2 - 1;
}
}
return 0;
}
编辑于 2021-04-02 11:51:19
回复(1)
写了个针对一般情况的。另外，如果总数是偶数，那么应该是第 N / 2 个和第 N / 2 + 1 个求平均（N为总长）。这里比较特殊，就按题目的要求来。
当然，最简单的就是合并两个有序数组然后找第 xx 个。时间复杂度为O(n)。
import java.util.*;
public class Solution {
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
int m = arr1.length, n = arr2.length;
if ((m + n) % 2 == 1) {
return findK(arr1, arr2, 0, m - 1, 0, n - 1, (m + n) / 2 + 1);
}
else {
return findK(arr1, arr2, 0, m - 1, 0, n - 1, (m + n) / 2);
}
}
//在两个有序数组中找第 K 个
private int findK(int[] a1, int[] a2, int l1, int r1, int l2, int r2, int k) {
//其中一方越界
if (l1 > r1)
return a2[l2 + k - 1];
if (l2 > r2)
return a1[l1 + k - 1];
//注意基本情况 k == 1
if (k == 1)
return Math.min(a1[l1], a2[l2]);
int ind1, len1, ind2, len2;
//优先考虑长度比较短的一方，正常来说应该要取 k / 2 个数，但是要考虑长度不够的情况
//另一方取的就是 k - 已经取了的
if (r1 - l1 <= r2 - l2) {
len1 = Math.min(k / 2, r1 - l1 + 1);
len2 = k - len1;
}
else {
len2 = Math.min(k / 2, r2 - l2 + 1);
len1 = k - len2;
}
ind1 = l1 + len1 - 1;
ind2 = l2 + len2 - 1;
//更新范围。小的一方后半段 + 大的一方前半段。
//更新k。小的一方前半段肯定在前 k 个的范围，减掉找剩下的
if (a1[ind1] <= a2[ind2]) {
return findK(a1, a2, ind1 + 1, r1, l2, ind2, k - len1);
}
else {
return findK(a1, a2, l1, r1, ind2 + 1, r2, k - len2);
}
}
}
编辑于 2021-03-25 14:24:18
回复(1)
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
//和leetcode的 两个有序数组的中位数 很像。
int l=0,r=arr1.length,mid=0;
int n=arr1.length;
if (n==0)
return 0;
int j=0;
while (l<=r){
mid=(l+r)/2;//往arr1中取出mid个数
j=n-mid;//往arr2中取出多少个数
int arr1_left=mid==0?Integer.MIN_VALUE:arr1[mid-1];
int arr1_right=mid==n?Integer.MAX_VALUE:arr1[mid];
int arr2_left=j==0?Integer.MIN_VALUE:arr2[j-1];
int arr2_right=j==n?Integer.MAX_VALUE:arr2[j];
int left_max=Math.max(arr1_left,arr2_left);
int right_min=Math.min(arr1_right,arr2_right);
if (left_max<right_min)
return left_max;
else if (arr1_left<arr2_left){
l=mid+1;
}else
r=mid;
}
return 0;
}
编辑于 2020-10-04 17:23:30
回复(0)
class Solution {
public:
vector<int> arr1; vector<int> arr2;
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
int n1 = arr1.size(); int n2 = arr2.size();
this->arr1.swap(arr1); this->arr2.swap(arr2);
return findKthMin(0, n1, 0, n2, (n1 + n2 + 1) / 2);
}
int findKthMin(int b1, int e1, int b2, int e2, int k) {
if(b1 == e1) return arr2[b2 + k - 1];
if(b2 == e2) return arr1[b1 + k - 1];
if(k == 1) return min(arr1[b1], arr2[b2]);
int m = min({k / 2, e1 - b1, e2 - b2});
if(arr1[b1 + m - 1] < arr2[b2 + m - 1])
return findKthMin(b1 + m, e1, b2, e2, k - m);
else
return findKthMin(b1, e1, b2 + m, e2, k - m);
}
};
发表于 2020-09-02 17:22:21
回复(0)
感觉题目埋了坑，只说有序数组，但没说升序降序，也没说两个数组排序是否相同，另外题目中上中位数定义感觉有问题
题目中的定义：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n个数
两个长度都为N的数组，合并后长度为2N，肯定为偶数，只需要输出两个数组中最大的数就行了，但和下面给的例子不符，偶数时上中位数应为第n/2个数
class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
//题目出的有漏洞，两个长度都为N的数组，合并后长度为2N，肯定为偶数
//按照题目中上中位数定义：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n个数
//只需要输出两个数组中最大的数就行了，偶数时上中位数应为第n/2个数
if(arr1.size()==0 && arr2.size() == 0)
{
return 0;
}
//如果有一个是空数组，返回另外一个数组的上中位数
if(arr1.size() == 0)
{
return midvalue(arr2);
}
if(arr2.size() == 0)
{
return midvalue(arr1);
}
int len = arr1.size()+arr2.size();
//计算上中位数坐标
int midindex = len/2;
if(len%2 == 0)
{
midindex -= 1;
}
int index1 = 0;
int step1 = 1;
int limit1 = arr1.size();
int min1 = arr1[0];
int max1 = arr1[arr1.size()-1];
int index2 = 0;
int step2 = 1;
int limit2 = arr2.size();
int min2 = arr2[0];
int max2 = arr2[arr2.size()-1];
if(min1 > max1)//数组1为降序，从尾部开始遍历
{
index1 = arr1.size()-1;
step1 = -1;
limit1 = 0;
min1 = arr1[arr1.size()-1];
max1 = arr1[0];
}
if(min2 > max2)//数组2为降序，从尾部开始遍历
{
index2 = arr2.size()-1;
step2 = -1;
limit2 = 0;
min2 = arr2[arr2.size()-1];
max2 = arr2[0];
}
//优化增加边界判断，如果一个数组的最小值大于等于另外一个数组的最大值，可以直接通过坐标值取得结果
if(min2 >= max1)
{
if(midindex < arr1.size())
{
if(step1 == 1)
{
return arr1[midindex];
}
else
{
return arr1[arr1.size() - 1 - midindex];
}
}
else
{
if(step2 == 1)
{
return arr2[midindex - arr1.size()];
}
else
{
return arr2[arr2.size() - 1 - midindex + arr1.size()];
}
}
}
if(min1 >= max2)
{
if(midindex < arr2.size())
{
if(step2 == 1)
{
return arr2[midindex];
}
else
{
return arr2[arr2.size() - 1 - midindex];
}
}
else
{
if(step1 == 1)
{
return arr1[midindex - arr2.size()];
}
else
{
return arr1[arr1.size() - 1 - midindex + arr2.size()];
}
}
}
for(int i=0;i<=midindex;i++)
{
if(i == midindex)
{
if(index1 != limit1 && index2 != limit2)
{
if(arr1[index1] < arr2[index2])
{
return arr1[index1];
}
else
{
return arr2[index2];
}
}
else if(index1 != limit1)
{
return arr1[index1];
}
else if(index2 != limit2)
{
return arr2[index2];
}
}
else
{
if(index1 != limit1 && index2 != limit2)
{
if(arr1[index1] < arr2[index2])
{
index1 += step1;
}
else
{
index2 += step2;
}
}
else if(index1 != limit1)
{
index1 += step1;
}
else if(index2 != limit2)
{
index1 += step1;
}
}
}
return 0;
}
int midvalue(vector<int>& arr)
{
int size = arr.size();
if(size%2 == 0)
{
if(arr[0] < arr[size-1])
{
return arr[size/2 - 1];
}
else
{
return arr[size/2];
}
}
else
{
return arr[size/2];
}
}
};
发表于 2020-08-28 14:57:40
回复(4)
这道题很难啊
class Solution {
public:/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int auxi(vector<int>& arr1, int p1, int p2, vector<int>& arr2, int q1, int q2) {
if (p1 == p2 - 1) {
return min(arr1[p1], arr2[q1]);
}
int mid1 = (p1 + p2) / 2;
int mid2 = (q1 + q2) / 2;
if ((p2 - p1) % 2 == 0) { // 偶数
if (arr1[mid1-1] == arr2[mid2-1]) return arr1[mid1-1];
else if (arr1[mid1-1] > arr2[mid2-1]) {
return auxi(arr1, p1, mid1, arr2, mid2, q2);
} else {
return auxi(arr1, mid1, p2, arr2, q1, mid2);
}
} else { // 奇数
if (arr1[mid1] == arr2[mid2]) return arr1[mid1];
else if (arr1[mid1] > arr2[mid2]) {
return auxi(arr1, p1, mid1+1, arr2, mid2, q2);
} else {
return auxi(arr1, mid1, p2, arr2, q1, mid2 + 1);
}
}
}
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
return auxi(arr1, 0, arr1.size(), arr2, 0, arr2.size());
}
};
发表于 2021-03-20 15:53:45
回复(2)
看到时间复杂度为O(logN)，很容易想到二分查找。过程如下：
-
如果每个数组中只有一个元素，较小的那个元素就是整体的上中位数，如果两个元素相等，随便返回哪个都可以。
-
如果数组中不止一个元素，找到两个数组的中间位置mid1和mid2。
-
如果arr1[mid1] == arr2[mid2]，不管每个数组中元素的个数是奇数还是偶数，这两个数都可以是整体的上中位数，返回其中一个就可以。
-
如果arr1[mid1] > arr2[mid2]，每个数组的个数是奇数的情况下：数组arr1中mid1位置以后的数都不可能是整体的上中位数，数组arr2中mid2位置以前的数都不可能是整体的上中位数。所以现在只需要考虑arr1[left1…mid1]、arr2[mid2…right]，这两部分的元素个数相同，它们的上中位数就是整体的上中位数。
-
如果arr1[mid1] > arr2[mid2]，每个数组的个数是偶数的情况下：数组arr1中mid1位置以后的数都不可能是整体的上中位数，数组arr2中mid2位置以后包括mid2位置，都不可能是整体的上中位数。所以现在只需要考虑arr1[left1…mid1]、arr2[mid2+1…right]，这两部分的元素个数相同，它们的上中位数就是整体的上中位数。
-
arr1[mid1] < arr2[mid2]的情况，分析同上。
class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
//由时间复杂度，想到二分查找
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
int n = arr1.size();
if(n==0){
return NULL;
}
//arr1左右两端
int l1=0,r1=n-1;
//arr2左右两端
int l2=0,r2=n-1;
int mid1,mid2;
//终止条件为l1=r1，即两个数组都只有一个元素，此时的上中位数为两数的最小值
while(l1< r1){
//arr1中位数
mid1 = l1+((r1-l1)>>1);
//arr2中位数
mid2 = l2+((r2-l2)>>1);
int k = r1-l1+1;
if(arr1[mid1] == arr2[mid2]){ //若两数组中位数相等，整体中位数也是这个
return arr1[mid1];
}
else if(arr1[mid1] > arr2[mid2]){
if(k%2 == 0){//区间元素个数为偶数
r1 = mid1; //整体中位数在arr1左区间,包括mid1
l2 = mid2+1; //整体中位数在arr2右区间，不包括mid2
}
else if(k%2 == 1){ //区间元素个数为奇数
r1 = mid1; //整体中位数在arr1左区间,包括mid1
l2 = mid2; //整体中位数在arr2右区间，包括mid2
}
}
else if (arr1[mid1] < arr2[mid2]){
if(k%2 == 0){//区间元素个数为偶数
r2 = mid2; //整体中位数在arr2左区间,包括mid2
l1 = mid1+1; //整体中位数在arr1右区间，不包括mid1
}
else if(k%2 == 1){ //区间元素个数为奇数
r2 = mid2; //整体中位数在arr2左区间,包括mid2
l1 = mid1; //整体中位数在arr1右区间，包括mid1
}
}
}
//当区间内只有一个元素时，两个区间中最小值即为整体中位数
return min(arr1[l1],arr2[l2]);
}
};
发表于 2020-09-01 11:34:17
回复(7)
思路一：思路就是从两个数组不断找较小者，找到第n个就返回。
class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
int l = 0, r = 0;
int res = 0;
while(l + r < arr1.size()){
if(arr2[r] < arr1[l])
res = arr2[r++];
else
res = arr1[l++];
}
return res;
}
}; 思路二：二分arr1，可以得到对应的arr2（保证arr1的前i个和arr2的前j个刚好凑够N个）
class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
int N = arr1.size();
int l = 0, r = N-1;
int res = 0;
while(l <= r){
int mid = (l+r)>>1;
if(mid == N-1)
return min(arr1[N-1], arr2[0]);
if(arr1[mid] == arr2[N-mid-2])
return arr1[mid];
if(arr1[mid] < arr2[N-mid-2]){
l = mid+1;
}
else
r = mid-1;
}
if(r < 0)
return min(arr1[0], arr2[N-1]);
int a = max(arr1[l], arr2[N-2-l]);
int b = max(arr1[r], arr2[N-2-r]);
return min(a, b);
}
};
编辑于 2020-08-31 20:38:30
回复(1)
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
int len = arr1.length;
int a1 = 0;
int a2 = 0;
while(len>1){
if(arr1[a1]<=arr2[a2])a1++;
else a2++;
len--;
}
return Math.min(arr1[a1],arr2[a2]);
}
不需要想的太复杂，既然题目说了是有序数组，那就双指针分别指向两个数组，按大小顺序
移动，移动次数为数组长度（题目中说的偶数奇数情况根本没用，因为两个数组长度相等，
不可能得到奇数个数字，中位数必然是第arr1.length个），指针移完了就取两个数组中小的。
发表于 2020-09-03 16:47:58
回复(5)
class Solution:
def findMedianinTwoSortedAray(self , arr1: List[int], arr2: List[int]) -> int:
for i in arr2:
arr1.append(i)
arr1.sort()
n=int(len(arr1)/2)
return(arr1[n-1])
发表于 2023-03-16 14:55:51
回复(0)
import java.util.*;
public class Solution {
/**
* find median in two sorted array
* @param arr1 int整型一维数组 the array1
* @param arr2 int整型一维数组 the array2
* @return int整型
*/
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
// write code here
int n = arr1.length;
int l = 0, r = 0,res = 0;
while(l + r < n) {
if(arr1[l] < arr2[r]) res = arr1[l++];
else res = arr2[r++];
}
return res;
}
}
发表于 2021-06-13 18:41:57
回复(1)
class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
int l1 = 0, r1 = arr1.size() - 1, l2 = 0, r2 = arr2.size() - 1;
while(l1 < r1){
int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;
//判断子区间的个数是奇数还是偶数 0代表是奇数（奇数中间的数字不能删除） 1代表是偶数
int even = (r1 - l1) % 2;
if(arr1[mid1] == arr2[mid2]){
return arr1[mid1];
} else if (arr1[mid1] > arr2[mid2]){
//证明arr1前面的子数组没用 arr2后面的子数组没用
// r1 = mid1 + even; //如果是奇数就是啥都不做
/*
3456 1234 得取34所有 l2 应该向后面取一位
*/
r1 = mid1;
l2 = mid2 + even;
} else {
l1 = mid1 + even; //如果是偶数 就是它的后一位
r2 = mid2;
}
}
//如果俩个数组剩下最后一个数 且不相等 返回其中较小的那个即可
return min(arr1[l1],arr2[l2]);
}
};
发表于 2021-04-01 17:00:32
回复(1)
import java.util.Arrays;
import java.util.stream.IntStream;
public class Solution {
public int findMedianinTwoSortedAray(int[] arr1, int[] arr2) {
int[] arr3 = IntStream.concat(Arrays.stream(arr1), Arrays.stream(arr2)).toArray();
Arrays.sort(arr3);
return arr3[(arr3.length -1) >> 1];
}
}
发表于 2024-04-27 09:52:38
回复(0)
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
// write code here
//上中位数的下标
int k = arr1.length - 1;
int i = 0, j = 0, s = 0;
//遍历两个数组，比较两个数组元素大小，直到遍历次数=上中位数的下标
while (i < arr1.length && j < arr2.length) {
if (arr1[i] <= arr2[j]) {
if (s == k) {
return arr1[i];
}
i++;
} else {
if (s == k) {
return arr2[j];
}
j++;
}
s++;
}
return 0;
}
发表于 2022-09-20 20:28:04
回复(0)
<pre class="prettyprint lang-java">//双指针白 public int findMedianinTwoSortedAray(int[] arr1, int[] arr2) { int n = (arr1.length + arr2.length + 1) / 2; int p1 = 0; int p2 = 0; int ans = 0; for (int i = 0; i < n; i++) { if (arr1[p1] <= arr2[p2]) ans = arr1[p1++]; else ans = arr2[p2++]; } return ans; }</pre> <br>
编辑于 2023-05-12 15:58:23
回复(1)
问题信息
难度：
96条回答
541收藏
6961浏览
通过挑战的用户
查看代码-
2022-12-23 10:51:46
-
2022-11-27 17:06:58
-
2022-09-28 02:02:49 -
2022-09-18 22:26:14
-
2022-09-16 16:22:54
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
