为了解决一个问题的一部分,其中我得到了 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,但是分配的内存很低。
最佳答案
来自 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
关于c++ - 找出数组中有多少个不同的浮点值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21968614/