c++ - 对索引值数组进行排序、打包和重新映射，以尽量减少重叠

Question

坐:

概览:

我有这样的东西:

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 是某种类型的数组(好吧，“vector ”)(与哪种类型无关)。 values 中的元素可能是唯一的，但不能保证这一点。

indexes 是一个整数 vector 。 "indexes"中的每个元素都是一个索引，对应于 values 中的某个元素。索引中的元素不是唯一的，一个值可能会重复多种类型。和 indexes.size() >= values.size()。

现在，范围 对应于索引 中的数据“ block ”。 firstElement 是 indexes 中要使用的元素的索引(即像这样使用:indexes[range.firstElement])，numElements(显然)是要使用的元素数，minIndex 是(索引中的最小值) [firstElement]...indexes[firstElement+numElements-1]) a,d maxIndex 在 (indexes[firstElement]...indexes[firstElement+numElements-1]) 中最大。范围从不重叠。IE。对于每两个范围 a, b

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

显然，当我对 values 进行任何操作(交换元素等)时，我需要更新索引(以便它们保持指向相同的值)，并重新计算相应的范围，因此范围的minIndex 和 maxIndex 是正确的。

现在，我需要以最小化 Range.maxIndex - Range.minIndex 的方式重新排列值。我不需要打包后的“最好”结果，拥有“可能最好”或“好”的打包就足够了。

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

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

限制:

不允许更改容器类型。容器应该是类似数组的。没有 map ，没有列表。但是您可以在分类过程中随意使用任何您想要的容器。此外，没有提升或外部库 - 纯 C++/STL，我真的只需要一个算法。

附加信息:

没有为 SomeType 定义更大/更小的比较 - 只有相等/不相等。但是应该不需要比较两个值，只需要比较索引。

算法的目标是保证

的输出

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

将在排序前后相同，同时还要确保对于每个范围Range.maxIndex-Range.minIndex(排序后)尽可能小，以合理的努力实现。我不是在寻找“完美”或“最佳”解决方案，拥有“可能完美”或“可能最佳”解决方案就足够了。

附言这不是作业。

Answer 1

这不是算法，只是一些大声思考。如果重复太多，它可能会崩溃。

如果没有重复项，您只需重新排列值，使索引为 0、1、2，依此类推。所以对于起点，让我们排除被双重引用的值并安排其余的

由于存在重复项，您需要弄清楚将它们粘贴到哪里。假设拷贝由范围 r1、r2、r3 引用。现在，只要在 min([r1,r2,r3].minIndex)-1 和 max([r1,r2,r3].maxIndex)+1 之间插入重复项，maxIndex-minIndex 的总和将相同无论您将其插入何处。将插入点向左移动会减小左侧所有范围的最大最小值，但会增加右侧所有范围的最大最小值。因此，我认为明智的做法是在 r1、r2、r3 的最右侧范围(具有最大 minIndex 的范围)的左边缘(minindex)插入拷贝。重复所有重复项。