424-分治算法-对数时间求中位数

小灰灰 2022-09-05 04:06 175阅读 0赞

## 分治算法-对数时间求中位数 ##

**对数时间：O(logn)**

**中位数：我们用长度除以2就知道在哪里了。  
但是题目有要求，在2个有序的数组当中，去求中位数。如果通过归并思想合并后求中位数，但是在合并的过程中，是O(n）的时间复杂度。**

## 中位数的概念 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]

## 问题描述 ##

![在这里插入图片描述][5c193375f8ff4cab988d4e4f0709550d.png]

## 解题思路 ##

**我们先画了2个数组（2个升序的数组）：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][24680debe8a840f7819a8075434213a5.png]

**我们现在的目的是：找这2个升序数组的第top k个元素**  
**我们在2个升序数组中找满足下列的条件：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]

**只要找到符号这个条件的ij的位置，就意味着在界限的左边的值全部小于界限的右边的值**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
（因为这2个数组本身就是升序的）  
因为arr\[0\]…arr\[i-1\]这部分本身就小于arr\[i\]…arr\[n\]  
brr\[0\]…brr\[j-1\]这部分本身就小于brr\[j\]…brr\[m\]  
所以，加上刚才列出来的条件：arr\[i-1\]<brr\[j\]&&brr\[j-1\]<arr\[i\]  
**所以得出下面这个结论：**  
![在这里插入图片描述][27ff76333b4349068eb660af63da8f75.png]  
如果我们找到了这样的i和j的位置，我们再来看：

**把界限左边的两段的元素个数相加，假如说个数是k，意味着第k个元素的值就是**  
![在这里插入图片描述][86a5b175eb0347f9802565c92ea3a3ba.png]  
**这2段序列一合并，这2个元素中的较大的那个元素就是在第k个！！！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]

**如果说，界限左边的合并的两段算出来的元素个数比k大，就说明我们不需要这么多元素，我们的i,j就可以往前推，即把多余的这些元素往界限后的区间段放。**  
把界限左边的末尾的元素依次往界限右边的区间段放，也就是把i和j下标往前推，但是依然是满足下面这个条件：  
![在这里插入图片描述][65a7f7fb0dc24fde8980140c22999eb7.png]  
**如果界限左边的合并的两段算出来的元素个数比k小，就把右边的元素往左拿，也是满足上面这个条件的，是不影响的！！！**

**所以，我们得出下面结论：**  
![在这里插入图片描述][3cbe39e2df4c40af9308dbbd97db8176.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]  
**所以：**  
![在这里插入图片描述][a5a34be668bf46e3a38e7999e9a71d8b.png]

## 如何找到这个分界的i和j的值？ ##

**O(logn)的时间就是花费在这里：找i和j的值**  
![在这里插入图片描述][2b65bda3971742e483e49f423f1cb03f.png]  
**看到O(logn)，我们就要联系到二分搜索树：**  
**我们看下面图解和代码：**  
begin是第一个数组的起始位置，end是第一个数组的末尾位置  
中间元素的下标我们定义为i=（begin+end）/2，二分之后，i的位置就是下图中的虚箭头指向的位置。  
因为我们要找第k个，所以既然在第一个数组里选择了i个，那么就要选择第二个数组的k-i个，j=k-i。i+j=k+k-k=k。总共就是k个  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]

**第k个元素就是**  
![在这里插入图片描述][783e5fe2e93e411196ac1c9432823226.png]  
**我们处理完，进行判断：**  
**如果说：**  
![在这里插入图片描述][24f05a66d81f43b29d35892b22fed85d.png]  
**就说明第k个已经找到了，已经找到i和j的位置了！**

**如果说：**  
![在这里插入图片描述][249588a0e7214b40b6bfa91a345acafc.png]  
**我们就要缩小二分搜索的范围，我们的end就要进行调整，end=i-1**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]

**如果说**  
![在这里插入图片描述][90c83c05a4ac4ee1a5ea1809d1c1152e.png]  
**我们就要从后面要找更大的，就是把begin往前推**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]

**我们用left来表示第k个元素：**  
然后分2个情况：总长度是奇数，总长度是偶数，这2种情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 8]  
**这一块操作是常量操作哦，比较两个数的大小，求一个和除以2或者直接返回left，这是常量操作。  
最终，算法的时间复杂度就是O(logn)**

## 对数时间求中位数代码实现 ##

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    //O(logn)对数时间求解中位数
    double middleValue(vector<int>& nums1, int length1, vector<int>& nums2, int length2)
    {
        
    	if (length1 > length2)
    	{
           //在短的数组中求解合适的i和j值，更快一点
    		return middleValue(nums2, length2, nums1, length1);
    	}
    
    	if (length1 == 0)
    	{
        
    		//0 0 0 0 0 0 0    (6-1)/2=3   
    		int k = (length2 - 1) / 2;
    		if (length2 % 2 == 0)
    		{
        
    			return (nums2[k] + nums2[k + 1]) * 1.0 / 2;
    		}
    		else
    		{
        
    			return nums2[k];
    		}
    	}
    
    	int i = 0;
    	int j = 0;
    	int begin = 0;
    	int end = length1;
    	int k = (length1 + length2 + 1) / 2; 
    	while (begin <= end)
    	{
           //二分搜索的算法思想，对数时间找到i+j = k
    		i = (begin + end) / 2;//在numbers1数组里面i的位置
    		j = k - i;//因为要满足i+j=k
    		if (i > 0 && j < length2 && nums1[i - 1] > nums2[j])
    		{
        
    			end = i - 1;//缩小二分搜索的范围，i前移，往前找
    		}
    		else if (j > 0 && i < length1 && nums2[j - 1] > nums1[i])
    		{
        
    			begin = i + 1;//i后退，往后找
    		}
    		else
    		{
        
    			break;//满足arr[i-1] < brr[j] && brr[j-1] < arr[i]，找到了
    		}
    	}
    
    	//我们有注意特别情况：nums1特别短，而且nums1数组的元素的值都特别大
    	//我们要找arr[i-1] < brr[j]
    	//nums1特别短，而且nums1数组的元素的值都特别大
    	//所以也就是i得一直前移找合适的i值，找不到，一直到i==0了
    	int left = 0;
    	if (i == 0)
    	{
           //中位数肯定都在num2这个数组当中
    		left = nums2[j - 1];
    	}
    	else if (j == 0)
    	{
           //nums2这个数组太短了  中位数肯定都在num1这个数组当中
    		left = nums1[i - 1];
    	}
    	else
    	{
        
    		left = std::max(nums1[i - 1], nums2[j - 1]);
    	}
    	int right = 0;
    	if (i == length1)
    	{
         //nums1数组元素太少，而且值都特别的小  中位数肯定都在num2这个数组当中
    	//我们要找：brr[j-1] < arr[i]，但是nums1数组元素太少，而且值都特别的小
    	//根本找不到brr[j-1] < arr[i],就要往i的右边一直缩小范围，i==lenth1代表找不到
    		right = nums2[j];
    	}
    	else if (j == length2)
    	{
           //中位数肯定都在num1这个数组当中
    	   //nums2数组元素太少，而且值都特别的小
    		right = nums1[i];
    	}
    	else//正常情况
    	{
        
    		right = std::min(nums1[i], nums2[j]);
    	}
    
    	//找到了合适的i和j的值
    	if ((length1 + length2) % 2 == 0)
    	{
           //偶数长度
    		return (left + right) * 1.0 / 2;//考虑结果可能是带有小数
    	}
    	else
    	{
           //奇数长度
    		return left;
    	}
    }
    int main()
    {
        
    	vector<int> vec1;
    	vector<int> vec2;
    	//for (int i = 0; i < 10; ++i) {
        
    	//	vec1.push_back(rand() % 100);
    	//}
    
    	for (int i = 0; i < 5; ++i)
    	{
        
    		vec2.push_back(rand() % 100);
    	}
    
    	vector<int> vec = vec1;
    	for (int v : vec2)
    	{
        
    		vec.push_back(v);
    	}
    	sort(vec.begin(), vec.end());
    	for (int v : vec)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    
    	sort(vec1.begin(), vec1.end());
    	sort(vec2.begin(), vec2.end());
    
    	double midval = middleValue(vec1, vec1.size(), vec2, vec2.size());
    	cout << "midval:" << midval << endl;
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 9]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/54cc9f4a5aad4dd598a5d7ae41821a1f.png
[5c193375f8ff4cab988d4e4f0709550d.png]: /images/20220829/83f0f9176df642b4acecd1f5dfefb0a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/de4a12d6055d4815a45c1eaa31d35c71.png
[24680debe8a840f7819a8075434213a5.png]: /images/20220829/367a1322d0d343a3a8647f0dd4315eaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/6c67a78f5daa4b7a9dba4ec26eda76ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/c51b2efe865d4f6a9ab0e20eef9e5faf.png
[27ff76333b4349068eb660af63da8f75.png]: /images/20220829/2e7ec03cb77d4c6285e2256861fc2dea.png
[86a5b175eb0347f9802565c92ea3a3ba.png]: /images/20220829/95d2c748927940319656f33d8f382169.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20220829/934d80ec860c4c348b4a025bba68e8ee.png
[65a7f7fb0dc24fde8980140c22999eb7.png]: /images/20220829/3dba73bd3ded44cfa3f0524d42e161f3.png
[3cbe39e2df4c40af9308dbbd97db8176.png]: /images/20220829/9d9ec81e4cc74b399ee8116ae30e1e19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]: /images/20220829/d9bb83bcbe654945a608c544853067de.png
[a5a34be668bf46e3a38e7999e9a71d8b.png]: /images/20220829/f578da5ff71b4525afe31d29d99fcc14.png
[2b65bda3971742e483e49f423f1cb03f.png]: /images/20220829/764979807d1d4f7e93da8b671d1cf644.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]: /images/20220829/da16b5512a874f40ae1b6795a9edba05.png
[783e5fe2e93e411196ac1c9432823226.png]: /images/20220829/4b7bdde045f442778cd5862cb4ab4ef5.png
[24f05a66d81f43b29d35892b22fed85d.png]: /images/20220829/2e6242a4e4b440b1aa0dce3c12ddd0ec.png
[249588a0e7214b40b6bfa91a345acafc.png]: /images/20220829/a6c7470d683b4b969b6e508d3e4e8007.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/8190d1e39da44440935d5d6032f175c4.png
[90c83c05a4ac4ee1a5ea1809d1c1152e.png]: /images/20220829/e6b7bb3cb66c48d893a092c680eddc8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]: /images/20220829/dfcdcea6603c4e9ba1dd36ab872a9c6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 8]: /images/20220829/ed994a1807ba414098fe2ceabbb5b134.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 9]: /images/20220829/89c0dd5517c149fbb4bda0c6524079a6.png