c – 对索引值的数组进行排序,打包和重新映射,以最大限度地减少重叠

概述Sitation： 概述： 我有这样的事情： std::vector<SomeType> values;std::vector<int> indexes;struct Range{ int firstElement;//first element to be used in indexes array int numElements;//number of element t Sitation：

概述：

我有这样的事情：

std::vector<SomeType> values;std::vector<int> indexes;struct Range{    int firstElement;//first element to be used in indexes array    int numElements;//number of element to be used from indexed array    int minIndex;/*minimum index encountered between firstElement         and firstElements+numElements*/    int maxIndex;/*maximum index encountered between firstElement         and firstElements+numElements*/    Range()        :firstElement(0),numElements(0),minIndex(0),maxIndex(0){    }}std::vector<Range> ranges;

我需要对值进行排序,重新映射索引并重新计算范围,以最小化每个范围的maxValueIndex-minValueIndex.

细节：

values是某种类型的数组(好的,“向量”)(与哪一种无关).值中的元素可能是唯一的,但这不能保证.

index是一个int的向量. “indices”中的每个元素都是与值中的某个元素对应的索引.索引中的元素不是唯一的,一个值可能会重复多种类型.而index.size()> = values.size().

现在,范围对应于索引的“数据块”数据. firstElement是要从索引中使用的元素的索引(即使用如下：indices [range.firstElement]),numElements是(显然)要使用的元素数,minIndex是mininum in(indices [firstElement] …索引[firstElement numElements-1])a,d maxIndex在(indices [firstElement] …索引[firstElement numElements-1])中是最大的.范围从不重叠.
即对于每两个范围a,b

((a.firstElement >= b.firstElement) && (a.firstElement < (b.firstElement+b.numElements)) == false

显然,当我对值进行任何 *** 作(交换到元素等)时,我需要更新索引(因此它们一直指向相同的值),并重新计算相应的范围,因此range的minIndex和maxIndex是正确的.

现在,我需要以最小化Range.maxIndex – Range.minIndex的方式重新排列值.包装后我不需要“最佳”结果,“可能最好”或“好”包装就足够了.

问题：
重新映射索引和重新计算范围很容易.问题是我不确定如何对值中的元素进行排序,因为在多个范围内可能会遇到相同的索引.

关于如何进行的任何想法？

限制：

不允许更改容器类型.容器应该是类似阵列的.没有地图,没有列表.
但是你可以在排序过程中随意使用你想要的任何容器.
此外,没有增强或外部库 – 纯C / STL,我真的只需要一个算法.

附加信息：

没有为SomeType定义更多/更少的比较 – 只有相等/不相等.
但是应该没有必要比较两个值,只有索引.

算法的目标是确保输出

for (int i = 0; i < indexes.size; i++){     print(values[indexes[i]]); //hypothetical print function}

在排序之前和之后将是相同的,同时也确保每个范围
Range.maxIndex-Range.minIndex(排序后)尽可能小,以合理的努力.
我不是在寻找一个“完美”或“最优”的解决方案,拥有“可能完美”或“可能是最优”的解决方案就足够了.

附：这不是一个功课.

解决方法 这不是算法,只是一些人大声思考.如果有太多重复,它可能会破坏.

如果没有重复项,您只需重新排列值,使索引为0,1,2,依此类推.因此,对于起点,让我们排除双引用的值并排列其余值

由于存在重复,您需要弄清楚它们的位置.假设副本由范围r1,r2,r3引用.现在,只要你在min([r1,r3] .minIndex)-1和max([r1,r3] .maxIndex)1之间插入副本,maxIndex-minIndex的总和就是相同的no插入它的地方.将插入点向左移动将减少左侧所有范围的max-min,但是将其增加到右侧的所有范围.因此,我认为明智的做法是在r1,r3的最右边范围(最大minIndex之一)的左边(minindex)插入副本.重复所有重复项.

总结

以上是内存溢出为你收集整理的c – 对索引值的数组进行排序,打包和重新映射,以最大限度地减少重叠全部内容，希望文章能够帮你解决c – 对索引值的数组进行排序,打包和重新映射,以最大限度地减少重叠所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。