时间戳

首页 > 解决方案 > 如何更改整数向量中的重复元素，以便在保持元素数量和单调性的同时不重复任何值？

c++ - 如何更改整数向量中的重复元素，以便在保持元素数量和单调性的同时不重复任何值？

问题描述

我有基于参数化方程生成从 0 到 1 的 N 个浮点分布的代码。我需要它们作为 8 位整数值，所以之后我将它们放大到 255 并将它们四舍五入到最接近的 int。我还需要它们是唯一的，没有重复的值。测试重复并删除它们相当简单，但是，我需要保留 N 个分布点的原始数量大小。在某些情况下，我可能已经有一个独特的集合，在这种情况下，不需要任何操作：

0 3 15 40 78 128 177 215 240 252 255 -> 无操作

但有时我可能会得到类似的结果：

0 0 0 2 21 128 234 253 255 255 255

在这种情况下，我想最终得到一个如下所示的集合：

0 1 2 3 21 128 234 252 253 254 255

我将每个重复值调整为使其唯一所需的最小值，同时保持单调顺序以及原始点数。

因此，从左到右，我需要做的是将第一个重复值增加 1，依此类推。但请注意，第 4 个元素是 2，因此我还需要考虑在增加其他值的同时创建副本的可能性。

但是在右侧，255 是我的最大可能值，所以我需要将它们向左递减 1。

我目前使用 Eigen 作为 Vector 容器，但我可以在 STL 中使用任何东西。

其他复杂情况是我无法提前知道原始点的数量 N，它可以是 2 到 255 之间的任何正整数。

另一个可能相关且有用的细节可能是我原来的从 0 到 1 的双精度分布集保证是唯一的且单调递增的。我不知道如何利用它，但如果有更好的解决方案，在扩展到 255 之前尝试计算重复是完全可以接受的。

这是当前生成双精度分布集然后将其缩放为整数的代码：

Eigen::VectorXi v_i(NUMBER_OF_POINTS);  // NUMBER_OF_POINTS: int from 2 to 255
Eigen::VectorXd v_d(NUMBER_OF_POINTS);
double d;

for ( int i = 1; i < v_d.size() - 1; ++i )
    {
        d = i / ( v_d.size() - 1.0 );
        v( i ) = 1.0 / ( 1.0 + pow( d / ( 1.0 - d ), -SLOPE ) );  // SLOPE: double > 0
    }

v_d( 0 ) = 0;  // Manually setting the endpoints to 0 and 1 to avoid divide by zero error 

v_d( v_d.size() - 1 ) = 1.0;

for ( int i = 0; i < v_i.size(); ++i )
{
    v_i(i) = round( v_d( i ) * 255 );
}

std::cout << v_i << std::endl;

在此先感谢您的帮助。

标签： c++vectoreigen

解决方案

解决这个问题的最简单方法是对数组进行两次遍历，假设它的排序开始于：

  • 前传，修改A[n] = A[n-1] + 1时间A[n] <= A[n-1]并钳位到 255
  • 反向传递，修改A[n] = A[n+1] - 1何时A[n] >= A[n+1]和（可选）钳位为 0

如果您的数组长度为 256 或更少，则可以保证所有元素都是唯一的。

它不一定是最佳的，也不能保证调整后的值尽可能接近其原始值，但这似乎不是您的要求之一。

任何比这更聪明的事情都可能需要大量的努力。

推荐阅读