C++中的唯一分数


假设我们有一组分数,每个分数包含[分子,分母](分子/分母)。我们需要找到一个新的分数列表,其中分数中的数字:

  • 已约分为最简分数。(20/14变为10/7)。

  • 删除任何重复的分数(约分后)。

  • 按实际值升序排列。

  • 如果数字为负数,则负号将与分子一起。

因此,如果输入类似于{{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-6, 12}},则输出将为[[-1, 2],[2, 1],[7, 3],[5, 1]]

为了解决这个问题,我们将遵循以下步骤:

  • 定义一个集合s

  • n := v的大小

  • 创建一个数组r

  • 初始化i := 0,当i < n时,更新(i加1),执行:

    • c := |v[i, 0]|和|v[i, 1]|的最大公约数

    • v[i, 0] := v[i, 0] / c

    • v[i, 1] := v[i, 1] / c

    • 将{v[i, 0], v[i, 1]}插入到r的末尾

  • 根据它们的值对数组r进行排序

  • 创建一个数组ret

  • 初始化i := 0,当i < r的大小 时,更新(i加1),执行:

    • 如果ret不为空且ret的最后一个元素与r[i]相同,则:

      • 将r[i]插入到ret的末尾

  • 返回ret

让我们看下面的实现来更好地理解:

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << "[";
      for (int j = 0; j < v[i].size(); j++) {
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]" << endl;
}
class Solution {
   public:
   static bool cmp(vector <int>& a, vector <int>& b){
      double aa = (double)a[0] / (double)a[1];
      double bb = (double)b[0] / (double)b[1];
      return aa < bb;
   }
   vector<vector<int>> solve(vector<vector<int>>& v) {
      set < vector <int> > s;
      int n = v.size();
      vector < vector <int> > r;
      for(int i = 0; i < n; i++){
         int c = __gcd(abs(v[i][0]), abs(v[i][1]));
         v[i][0] /= c;
         v[i][1] /= c;
         r.push_back({v[i][0], v[i][1]});
      }
      sort(r.begin(), r.end(), cmp);
      vector < vector <int> > ret;
      for(int i = 0; i < r.size(); i++){
         if(!ret.empty() && ret.back() == r[i]) continue;
         ret.push_back(r[i]);
      }
      return ret;
   }
};
int main(){
   vector<vector<int>> v = {{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-
   6, 12}};
   Solution ob;
   print_vector(ob.solve(v));
}

输入

{{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-6, 12}}

输出

[[-1, 2, ],[2, 1, ],[7, 3, ],[5, 1, ],]

更新于:2020年9月2日

210 次查看

启动您的职业生涯

通过完成课程获得认证

开始学习
广告