数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究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 次查看
广告