1

为了解决问题中的一部分，其中给定n对整数x和y，我需要找出有多少不同的x/y。（精确值，带小数）

1.

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

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

2.

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

  • 计算每对的最大公约数
  • 将x和y与 GCD相除

  • 使用矩阵 m[max_value_of_x][max_value_of_y] 并执行以下操作：

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

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

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

4

3 回答 3

1

从 MBo 使用 set 的解决方案：

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
于 2014-02-23T13:56:59.517 回答
0

您可以将 x/y 对存储在列表或数组中，并使用比较器函数对该列表进行排序，该函数比较 x1*y2 和 x2*y1 - 请注意，所有计算都是整数。排序后（NlogN），遍历列表并计算不同的值（仅比较邻居）

于 2014-02-23T13:41:23.767 回答
0

另一种方法可以将所有 x/y 值存储在一个集合中并避免重复条目。这可以通过

      set < float > store ; // choose the datatype according to the precison needed .
      // If arr[] is the given array containing pair x and y .
      store . clear () ; .
      for ( i = 0 ; i < arr.size() ; i++)
       {  x = arr[i].first ; y = arr[i].second ;
          float y = (x/gcd(x,y) / (y/gcd(x,y)) ; // For precison round the values   
           store.insert ( y ) ;
        }
于 2014-02-23T14:00:46.327 回答