int getKth(vector<int>& nums1,int l1,int r1,vector<int>& nums2,int l2,int r2, int K)
{
int half_k = K/2; //每次访问各组的K/2处的元素，以便缩小数组规模
int len1 = r1 - l1; //记录数组1的大小
int len2 = r2 - l2; // 记录数组2的大小
if(len2Kth(nums2,l2,r2,nums2,l1,r1,K); //保证nums1始终是较短的数组
if(K==1) return nums1[l1][l2]?nums1[l1]:nums2[l2]; //出口1
if(len1==0) return nums2[l2+K-1]; //出口2
int i = l1+min(half_k,len1)-1; //K/2加上half_K有可能超出数组的长度，所以加上min；i指向l1中的K/2或者末尾元素
int j = l2+min(half_k,len2)-1; //j指向l1中的K/2或者末尾元素
if(nums1[i][j]) //因为这两个数组都是递增有序，所以较小的那个元素所在的数组左边那一半就可以被排除
{
getKth(nums1,i+1,r1,nums2,l2,r2,K-(i-l1+1)); //K要随着数组范围的缩小而改变
}
else
{
getKth(nums1,l1,r1,nums2,j+1,r2,K-(j-l1+1));
}
}
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int l1 = 0,r1 = nums1.size();
int l2 = 0,r2 = nums2.size();
int left = (r1+r2+1)/2; //巧妙地处理奇数和偶数时中位数的位序
int right = (r1+r2+2)/2;
double ans = (getKth(nums1,l1,r1,nums2,l2,r2,left)+getKth(nums1,l1,r1,nums2,l2,r2,right))/2.0;
return ans;
}
};
leetcode里heap overflow，请问怎么优化呀？
heap overflow，看看是不是分配了超过需求的内存，或者有内存没有释放，检查下。
该回答引用GPTᴼᴾᴱᴺᴬᴵ
在这个实现中，getKth函数的时间复杂度是O(log(m+n))，其中m和n分别是nums1和nums2的长度。由于是递归调用，每次调用会创建新的栈帧，如果输入的nums1和nums2非常大，会导致栈溢出（stack overflow）。
·
为了解决这个问题，我们可以将递归改为迭代。具体来说，我们可以用while循环来代替递归调用。在每次循环中，我们通过比较nums1和nums2中的第K/2个元素来排除K/2个元素，并根据剩余元素的个数来更新左右指针。
下面是修改后的代码：
int getKth(vector<int>& nums1, int l1, int r1, vector<int>& nums2, int l2, int r2, int K) {
while (true) {
int len1 = r1 - l1;
int len2 = r2 - l2;
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 i = l1 + min(len1, K / 2) - 1;
int j = l2 + min(len2, K / 2) - 1;
if (nums1[i] < nums2[j]) {
K -= (i - l1 + 1);
l1 = i + 1;
} else {
K -= (j - l2 + 1);
l2 = j + 1;
}
}
}
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
int k1 = (m + n + 1) / 2;
int k2 = (m + n + 2) / 2;
return (getKth(nums1, 0, m, nums2, 0, n, k1) + getKth(nums1, 0, m, nums2, 0, n, k2)) / 2.0;
}
};
在这个实现中，我们将递归调用改为while循环，并使用l1和r1分别表示nums1中当前搜索区间的左右指针，l2和r2表示nums2中当前搜索区间的左右指针。在每次循环中，我们计算len1和len2来表示当前搜索区间的大小，然后比较nums1和nums2中的第K/2个元素，并排除较小的那个元素及其左边的所有元素。
·
我们使用变量i和j来表示被排除的元素的下标，然后根据i和j的位置更新左右指针和K的值。如果nums1[i]<nums2[j]，则表明nums1的前i个元素都不可能是第K个元素，我们将l和i+1作为下一轮查找nums1的范围，同时将K减去i-l+1（i和l都是上一轮查找中的值），表示已经排除了i-l+1个元素。如果nums1[i]>=nums2[j]，则表明nums2的前j个元素都不可能是第K个元素，我们将j+1和r2作为下一轮查找nums2的范围，同时将K减去j-l+1。
·
由于每次查找都会将数组范围减半，因此算法的时间复杂度为O(log(m+n))，其中m和n分别是两个输入数组的长度。
·
至于heap overflow的问题，这可能是由于输入的数据太大，导致内存不足。可以考虑对输入的数据进行分批处理，逐步处理每一批数据，并释放之前的数据，以避免内存溢出。同时，也可以考虑优化代码实现，减少内存使用。