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

Question

我有代码可以根据参数化方程生成从 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;

在此先感谢您的帮助。

Answer 1

解决此问题的最简单方法是对数组执行两次遍历，假设它是从以下位置开始排序的：

前向传球，在 A[n] <= A[n-1] 时修改 A[n] = A[n-1] + 1 并固定到 255
反向传递，在 A[n] >= A[n+1] 时修改 A[n] = A[n+1] - 1 并且（可选）固定为 0

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

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

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

Answer 2

您可以从 0,1,...,255 的向量开始，对其进行打乱，然后对前 N 个元素进行排序。可以使用前缀总和在常数时间内完成排序：

#include <random>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <iostream>
#include <Eigen/Dense>
using namespace Eigen;
using namespace std;

int main()
{
  VectorXi base = VectorXi::LinSpaced(256,0,255); 
  std::random_device rd;
  std::mt19937 g(rd());
  std::shuffle(base.begin(), base.end(), g);
  int N = 10;

  std::cout << base.head(N).transpose() << "\n";

  // explicit sort
  {
    VectorXi A = base.head(N);
    std::sort(A.begin(), A.end());
    std::cout << A.transpose() << "\n";
  }

  // no sort but O(256) pass
  {
    VectorXi mask = VectorXi::Zero(256), pos(256);
    mask(base.head(N)).fill(1);
    std::partial_sum (mask.begin(), mask.end(), pos.begin());
    VectorXi A(N);
    for(auto i:base.head(N))
      A(pos[i]-1) = i;
    std::cout << A.transpose() << "\n";
  }

  // same with fused partial_sum
  {
    VectorXi mask = VectorXi::Zero(256);
    mask(base.head(N)).fill(1);
    VectorXi A(N);
    int c = 0;
    for(int i=0,c=0; i<256; ++i)
      if(mask[i])
        A(c++) = i;
    std::cout << A.transpose() << "\n";
  }
}

要使 begin()/end()/range-for-loop 工作，您需要 Eigen 的头部，但您可以将前者替换为 vec.data(), vec.data()+vec.size()，将后者替换为经典的 for 循环。

Answer 3

@paddy 给出的答案是我解决方案的基础。为了社区的完整性，下面是为我解决问题的实际代码。我敢肯定它不是最有效的，但它可以完成工作，并且对于小于 1000 的数据集具有足够的性能，就像我的情况一样。

假设我的问题数据存储在 Eigen::VectorXi v_int

Eigen::VectorXi v_int_unique = v_int; // Beginning and end values never change 
                                      // middle value won't change if v_int.size() is odd

for ( int i = 1; i < v_int.size() / 2; ++i )
{
    if ( v_int( i ) == v_int( i - 1 ) )
    {
        v_int_unique( i ) = v_int( i ) + 1;
    }

    if ( v_int( i ) < v_int_unique( i - 1 ) )
    {
        v_int_unique( i ) = v_int_unique( i - 1 ) + 1;
    }

}

for ( int i = v_int.size() - 2; i > v_int.size() / 2; --i )
{
    if ( v_int( i ) == v_int( i + 1 ) )
    {
        v_int_unique( i ) =  v_int( i ) - 1;
    }

    if ( v_int( i ) > v_int_unique( i + 1 ) )
    {
        v_int_unique( i ) = v_int_unique( i + 1 ) - 1;
    }

}

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

How can I change duplicate elements in a vector of ints so no values are repeated while also maintaining the number of elements and monotonicity?

c++

vector

eigen