清华计算几何-ElementUniqueness, MinMap, MaxGap

ElementUniqueness问题(EU)

给出一组数给出一组数据,, 判断每个数都是唯一性的或者说判断是否存在重复的.

算法思路很简单, 快速排序 + 遍历判断: Max(O(nlogn) + O(n)) = O(nlogn)算法复杂度

代码实现

bool IsEelementUniqueness(const vector<float>& Elemnts)
{vector<float> TempElemnts = Elemnts;sort(TempElemnts.begin(), TempElemnts.end());for (int index = 0; index < TempElemnts.size() - 1; index++){if(TempElemnts[index] == TempElemnts[index + 1])return false;}return true;
}

	vector<float> floatValues = { 4.5f, 2.0f, 3.0f, 2.0f, 1.0f, 1.3f};if (IsEelementUniqueness(floatValues)){printf("Element uniequeness\n");}else{printf("not element uniequeness\n");}

MinMap和MaxGap问题

MinMap

给出一组数，求相邻两个数的最小间距

求解算法和上面 "EU"问题是同个问题. 相邻两个数最小间距不为0时, 则满足EU，反过来不满足EU.

MaxMap

给出一组数，求相邻两个数的最大间距 

用桶分法:

[1]求出最大和最小值MaxValue和MinValue

[2]n个数，则设计n个Section区间,  SectionLength = (MaxValue - MinValue) / (n - 2)。每个Section存在: 数的数量, 最大值, 最小值

class SectionBucket
{
public:float maxValue;float minValue;int count;SectionBucket(){maxValue = FLT_MIN;minValue = FLT_MAX;count = 0;}
};

[3]遍历所有数, 并且把相应的数用除法划分到相应的区间，并更新该区间的最大和最小值

[4]最后遍历所有的Section, 求取前后两个相邻Section的最大间距.(后Section的最小值减去前Section的最大值)

代码实现

float GetMaxCap(const vector<float>& Elemnts)
{float maxValue = FLT_MIN;float minValue = FLT_MAX;// get max value and min valuefor (int index = 0; index < Elemnts.size(); index++){if (Elemnts[index] > maxValue){maxValue = Elemnts[index];}if (Elemnts[index] < minValue){minValue = Elemnts[index];}}int n = Elemnts.size();vector<SectionBucket> buckets;buckets.resize(n);float bucketSize = (maxValue - minValue) / (float)(n - 1);for (int index = 0; index < n; index++){int bucketIndex = int((Elemnts[index] - minValue) / bucketSize) + 1;if (bucketIndex == n)bucketIndex = n - 1;buckets[bucketIndex].count++;if (Elemnts[index] > buckets[bucketIndex].maxValue){buckets[bucketIndex].maxValue = Elemnts[index];}if (Elemnts[index] < buckets[bucketIndex].minValue){buckets[bucketIndex].minValue = Elemnts[index];}}// bucket index from 1 to n - 1 float cap = 0.0f;float leftValue = buckets[1].maxValue;for (int index = 2; index < n; index++){if (buckets[index].count > 0){float distance = buckets[index].minValue - leftValue;if (distance > cap){cap = distance;}leftValue = buckets[index].maxValue;}}return cap;
}

测试

	vector<float> floatValues = { 4.5f, 2.0f, 3.0f, 2.0f, 1.0f, 1.3f };float maxCap = GetMaxCap(floatValues);printf("MaxCap = %f\n", maxCap);

算法复杂度

从代码实现很显然MaxCap算法复杂度是O(n)

参考资料

[1]清华计算几何 P61-P65