c++ - 找出数组中有多少个不同的浮点值

Question

为了解决一个问题的一部分，其中我得到了 n 对整数 x 和 y，我需要找出有多少个不同的x/y。 (精确值，带小数点)

1.

当然，我可以遍历之前的所有对，看看之前是否出现过相同的 x/y 值，但我相信这需要 (n^2)/2 次。

我尝试使用哈希表，它似乎不能很好地处理浮点值。也许它可以与非常好的哈希函数一起使用。

2.

考虑到 x 和 y 是整数，我尝试了一种不同的方法来解决这个问题:

• 计算每对的最大公约数
• 用 GCD 划分 x 和 y

• 使用矩阵 m[max_value_of_x][max_value_of_y] 并执行此操作:

  if ( m[x][y] ) { ; } else { m[x][y] = 1 ; cnt++ ; } 
  

• 对所有对执行此操作后，cnt 应该是不同浮点值的数量。

尽管我认为这可以在相当长的时间内运行；它绝对不节省空间。实际上在这个问题中，x和y的最大值是1000，但是分配的内存很低。

Answer 1

来自 MBo 使用集合的解决方案:

struct cmp_div {
    bool operator ()(const std::pair<int, int>& xy1, const std::pair<int, int>& xy2) const {
        // x1/y1 < x2/y2
        return xy1.first*xy2.second < xy2.first*xy1.second;
    }
};

std::set<std::pair<int, int>, cmp_div> c;
c.emplace(6, 2);
c.emplace(9, 3);
std::cout << c.size(); // == 1