Min Diff of A Array

1月 24 2015

这题是高级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

Posted by richard爱闹 - 1月 24 2015
如需转载，请注明：本文来自 Richard

留言