【算法】一维最接近点对问题

---

一、描述

• 一维最接近点对问题：也就是寻找无序不重复数组的最小差值
• 解题思想：分治策略

二、思路

三、代码

//寻找非负整数序列(不重复)的最小差值
#if 1
//两边向中间划分
int OnePartition(int* arr, int left, int right)
{
	int tmp = arr[left];
	int i = left;
	int j = right;
	while (i < j)
	{
		while (i < j && arr[j] > tmp)
		{
			--j;
		}
		arr[i] = arr[j];
		while (i < j && arr[i] <= tmp)
		{
			++i;
		}
		arr[j] = arr[i];
	}
	arr[i] = tmp;
	return i;
}
//findK
int FindK(int* arr, int left, int right, int k)
{
	if (left == right && k == 1) return arr[left];
	int mid = OnePartition(arr, left, right);
	int kmin = mid - left + 1;	//arr[mid]是kmin小
	//第k小在mid左边(arr, left, mid, k)
	if (k <= kmin)
	{
		return FindK(arr, left, mid, k);
	}
	//k小在mid右边
	else
	{
		return FindK(arr, mid + 1, right, k - kmin);
	}
}

int Max_arr(int* arr, int left, int right)
{
	return arr[left];
}
int Min_arr(int* arr, int left, int right)
{
	int min = arr[left];
	for (int i = 1; i <= right; ++i)
	{
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	return min;
}
int Min(int a, int b)
{
	return a > b ? b : a;
}
int Min(int a, int b, int c)
{
	return (Min(a, b), c);
}
int FindMS(int* arr, int left, int right)
{
	if (right <= left) return INT_MAX;
	//优化分割（两边近似等长）
	int k = (right - left + 1) / 2;
	FindK(arr, left, right, k);
	int midpos = left + (k - 1);
	//左区间内
	int d1 = FindMS(arr, left, midpos);
	//右区间内
	int d2 = FindMS(arr, midpos + 1, right);
	
	//两个区间之间差值
	int maxleft = Max_arr(arr, left, midpos);
	int minright = Min_arr(arr, midpos + 1, right);
	return Min(d1, d2, minright - maxleft);
}
int FindMinSub(int* arr, int len)
{
	if (arr == nullptr || len < 2 ) return -1;
	return FindMS(arr, 0, len - 1);
}
int main()
{
	int arr[] = { 56, 12, 15, 45, 89, 86, 46, 57, 26, 33 };
	int len = sizeof(arr) / sizeof(arr[0]);
	cout << FindMinSub(arr, len) << endl;
	return 0;
}
#endif