leetcode 寻找两个正序数组的中位数

╰+攻爆jí腚メ 2022-11-21 15:08 185阅读 0赞

### 题意： ###

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

### 思路： ###

> 首先假设两个数组大小分别为n和m，如果(n + m)为奇数的话我们需要找到第(n + m + 1) / 2个元素；如果(n + m)为偶数的话我们需要找到第(n + m) / 2 和 (n + m) / 2 + 1个元素，现在我们定义一个函数来找到两个数组中第k大的元素。
> 
> 我们设x = k/2 - 1, 现在比较nums1\[x\] 与 nums2\[x\]的大小关系
> 
>  *  nums1\[x\] < nums2\[x\] : 那么nums1\[0\] ~ nums1\[x\]之间的元素一定不可能是第k大的元素
>  *  nums1\[x\] > nums2\[x\] : 同理，nums2\[0\] ~ nums2\[x\]之间的元素一定不可能是第k大的元素
>  *  nums1\[x\] = nums2\[x\]：可以当做第一种情况处理
> 
> 用两个指针分别记录两个数组的偏移量，每次移动记录偏移位置，并更新k的值，注意边界即可。

时间复杂度：O(log(n + m)) 空间复杂度：O(1)

class Solution 
    { 
    public:
    	int get_kth(vector<int>& nums1, vector<int>& nums2, int k)
    	{ 
    		int px = 0, py = 0;
    		while(k >= 1)
    		{ 
    			if(px == nums1.size()) return nums2[py + k - 1];
    			if(py == nums2.size()) return nums1[px + k - 1];
    			if(k == 1) return min(nums1[px], nums2[py]);
    			int id1 = px + k / 2 - 1, id2 = py + k / 2 - 1;
    			if(id1 > (int)nums1.size() - 1) id1 = nums1.size() - 1;
    			if(id2 > (int)nums2.size() - 1) id2 = nums2.size() - 1;
    			if(nums1[id1] <= nums2[id2])
    			{ 
    				k = k - (id1 - px + 1);
    				px = id1 + 1;
    			}
    			else if(nums1[id1] > nums2[id2])
    			{ 
    				k = k - (id2 - py + 1);
    				py = id2 + 1;
    			}
    		}
            return min(nums1[px], nums2[py]);
    	}
    	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    	{ 
    		int n = nums1.size(), m = nums2.size();
    		if((n + m) & 1)
    		{ 
    			return (double)get_kth(nums1, nums2, (n + m) /2 + 1);
    		}
    		return 1.0 * (get_kth(nums1, nums2, (n + m) >> 1) + get_kth(nums1, nums2, (n + m) / 2 + 1)) / 2;
    	}
    };