Min Diff of A Array
这题是高级C++群里有人问，结果学神还很不屑的和群里人争论起来，除了智商和勤奋的压制，我没有什么好说的了。
这题学神提示也是鸽笼原理，我想起来lc上的maxgap题，于是朝这里想，发现似乎不太一样，每个桶里面似乎还需要再进一步看，
考虑到mcgrill 课件是 去掉max 和min 元素将n-2个元素丢到n-1个桶里，我是觉得 全部统一一起比较好。
n个元素 丢到 n 个桶，最后一个桶 一定只有一个元素，类似于左臂右开的区间。然后对于<=1个元素的通丢弃，其余的通分治一下，
另外还需要处理相邻桶之间的max min 的diff， 所以代码如下。由于至少存在一个 桶元素<=1个的，因此分治一定可以结束
至于时间复杂度，我是有点怀疑，瞿神说这个可以证明是ON的。感觉应该不是ON的，因为有个分治，似乎会影响时间复杂度
#include<set>
#include<map>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<cstdio>
#include<string>
#include<vector>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long LL;
typedef unsigned long long ULL;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define mp make_pair
#define pb push_back
#define CLR(a,x) memset(a,x,sizeof(a))
struct bucket
{
vector<int> data;
int maxe=INT_MIN, mine=INT_MAX;
};
int MinDiff(vector<int> num)
{
int n=num.size();
if(n<=1) return 0;
if(n==2) return abs(num[0]-num[1]);
bucket datas[n];
int ttmax=*max_element(num.begin(), num.end());
int ttmin=*min_element(num.begin(), num.end());
for(auto i: num)
{
int bucketi=(i-ttmin)/(ttmax-ttmin);
datas[bucketi].data.push_back(i);
datas[bucketi].maxe=max(datas[bucketi].maxe, i);
datas[bucketi].mine=min(datas[bucketi].mine, i);
}
int save=0;
for(int i=0;i<n;i++) if(datas[i].data.size()) datas[save++]=datas[i];
if(save<=1) return MinDiff(datas[0].data);
int mindiff=datas[1].mine-datas[0].maxe;
for(int i=2;i<save;i++) mindiff=datas[i].mine-datas[i-1].maxe;
for(int i=0;i<save;i++)
{
if(datas[i].data.size()>=2) mindiff=min(mindiff, MinDiff(datas[i].data));
}
return mindiff;
}
int main()
{
vector<int> num={34,54,547,2457,574,38,734,7,347,4,435,2364,634,2360};
cout<<MinDiff(num)<<endl;
return 0;
}
搞了半天，原来是排序做的题目
另外附上max gap的代码，相比之下 maxgap代码更简单
struct bucket
{
int maxe = 0, mine = INT_MAX;
int elenum = 0;
};
class Solution {
public:
int maximumGap(vector<int> &num) {
int n=num.size();
if(n<2) return 0;
int maxe=*max_element(num.begin(), num.end());
int mine=*min_element(num.begin(), num.end());
double bucketsize = (double)(maxe-mine) / (n-1);
bucket data[n];
for(auto i:num)
{
int bucketid= (i-mine)/bucketsize;
data[bucketid].maxe=max(data[bucketid].maxe, i);
data[bucketid].mine=min(data[bucketid].mine, i);
data[bucketid].elenum++;
}
int save=0;
for(int i=0;i<n;i++)
if(data[i].elenum)
data[save++]=data[i];
if(save<=1) return data[0].maxe - data[0].mine;
int maxgap=data[1].mine-data[0].maxe;
for(int i=1;i<save-1;i++)
maxgap=max(data[i+1].mine-data[i].maxe,maxgap);
return maxgap;
}
};
从这题也逐渐摸索出鸽笼原理怎么运用到算法里面，类似于桶的做法
Windows分区如果是动态分区的话，就是一整块，要将动态磁盘转换为基本磁盘，才可以真正分出逻辑分区，然后可以安装Ubuntu