leetcode 劝退题 花了7个小时 还算是基本能解出来 一些边界条件还是很模糊
尾扫描
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int k1 = (m+n)/2;
int k2 = (m+n)/2+1;
double value1 = find_num(k2, nums1 , nums2);
if((m+n)%2 != 0) {
return value1;
}
double value2 = find_num(k1, nums1 , nums2);
return (value1+value2)/2;
}
public static double find_num(int k , int [] nums1 , int[] nums2) {
double ans = 0;
int m = nums1.length-1;
int n = nums2.length-1;
while(k>0&&m>=0&&n>=0) {
k--;
int temp1 = nums1[m];
int temp2 = nums2[n];
if(temp1>temp2) {
ans = temp1;
m--;
}
else {
ans = temp2;
n--;
}
}
while(k>0&&m>=0) {
ans = nums1[m];
m--;
k--;
}
while(k>0&&n>=0) {
ans = nums2[n];
n--;
k--;
}
return ans ;
}
}
二分
第一步 思路有点问题 修改为 第k/2必定在矩阵里面
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length + nums2.length;
if(total%2==0) {
int value1 = findKth(nums1 ,0 ,nums2 ,0 ,total/2+1);
int value2 = findKth(nums1 ,0 ,nums2 ,0 ,total/2 );
return (value1+value2)/2.0;
}
else
return findKth(nums1 ,0 ,nums2 ,0 ,total/2+1);
}
public static int findKth(int nums1[] , int i ,int []nums2 , int j ,int k) {
if(nums1.length- i > nums2.length - j )return findKth(nums2, j, nums1, i, k);
if(nums1.length == i)return nums2[j + k - 1];
if(k==1)return Math.min(nums1[i],nums2[j]);
int si = Math.min(i + k / 2,nums1.length);
int sj = j + k /2 ;
if(nums1[si-1]>nums2[sj-1]) {
return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
}
else return findKth(nums1, si, nums2, j, k - (si - i));
}
}
第一步 思路有点问题 修改为 第k/2必定在矩阵里面
一直把能两个数组使用的区域 尽量用nums1接受小的 这样就省去了 要判断nums1 和nums2 是否溢出 这样就会很麻烦 所以一直用nums1来接收小的可用区域数组即可