279-寻找最小差值的问题

Myth丶恋晨 2023-01-14 13:56 123阅读 0赞

## 寻找最接近的点 ##

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

## 寻找最小差值的问题 ##

假设我们有一个数组，数组中的数据并没有进行排序，通过找第k位小的，会给出一个m值，把数据进行划分，并没有排序，m的位置不动，s1<=m，s2>m  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
我们在m的左边找一个d1，右边找一个d2，然后在左边找到最大值，在右边找到最小值，相减得到d3。  
**为什么在s1找最大值，s2找最小值？**  
我们在划分的时候，找的是第k小的数据，有一个数据是m，s1的所有值均小于等于m，s2的所有值均大于m，在s1找最大值，在s2找最小值，相减值（差值）就是最小的！

## 寻找最小差值的代码 ##

#include<iostream>
    #include<limits.h>
    using namespace std;
    
    //#define INT_MAX   2147483647
    int Parition(vector<int>& br, int left, int right)//划分函数 
    {
        
    	int i = left, j = right;
    	int tmp = br[i];
    	while (i < j)
    	{
        
    		while (i < j && br[j] > tmp) --j;
    		if (i < j) br[i] = br[j];
    		while (i < j && br[i] <= tmp) ++i;
    		if (i < j) br[j] = br[i];
    	}
    	br[i] = tmp;
    	return i;
    }
    
    int Select_K(vector<int>& br, int left, int right, int k)//寻找第k位小的数据 
    {
        
    	if (left == right && k == 1) return br[left];
    	int index = Parition(br, left, right);
    	int pos = (index - left + 1);
    	if (k <= pos) return Select_K(br, left, index, k);
    	else return Select_K(br, index + 1, right, k - pos);
    } 
    
    int Min_Int(int a, int b)
    {
        
    	return a < b ? a : b;
    }
    int Min3(int a, int b, int c)
    {
        
    	return Min_Int(a, Min_Int(b, c));
    }
    int MaxS1(vector<int>& br, int left, int right)
    {
        
    	return br[right];
    }
    int MinS2(vector<int>& br, int left, int right)
    {
        
    	int min = br[left];
    	for (int i = left + 1; i <= right; ++i)
    	{
        
    		if (min > br[i])
    		{
        
    			min = br[i];
    		}
    	}
    	return min;
    }
    int Cpair(vector<int>& br, int left, int right)//寻找最小差值的函数 
    {
        
    	if (right - left < 1) return INT_MAX; //只有1个数据，返回初始化的最大值 
    	int k = (right - left + 1) / 2;//寻找中的下标 
    
    	Select_K(br, left, right, k);//调动，寻找第k小的数据值，进行划分 
    	int d1 = Cpair(br, left, left + k -1); // s1区域 
    	int d2 = Cpair(br, left + k, right); // s2区域 
    
    	int p = MaxS1(br, left,left + k - 1); // s1的最大值 
    	int q = MinS2(br, left + k, right);// s2的最小值 
    
    	return Min3(d1, d2, q - p);//返回最小差值 
    }
    int main()
    {
        
    	vector<int> ar = {
         14,56,34,100,23,78,93,12,45,67,88 };
    	
    	int dist = Cpair(ar, 0, ar.size() - 1);
    
    	cout << dist << endl;
    	return 0;
    }

## 运行程序 ##

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/c7038f2e403f4e398a5b69e17e2b9659.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/144f4006c20f4a5381f5bef5420c64a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/1b8e7d33c42246e59a7cd9ce4ea9f28a.png