資料結構
網路
關係資料庫管理系統(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 次檢視
廣告