You are given a list of lists fractions
where each list contains [numerator, denominator]
which represents the number numerator / denominator
.
Return a new list of lists such that the numbers in fractions
are:
 In their most reduced terms. E.g.
8 / 6
becomes4 / 3
.  Any duplicate fractions that represent the same value are removed.
 Sorted in ascending order by their value.
 If the number is negative, the sign should go to the
numerator
(the input also follows this).
Constraints

n ≤ 100,000
wheren
is the length offractions
Example
fractions = [
[8, 4],
[2, 1],
[7, 3],
[14, 6],
[10, 2],
[3, 6]
]
Output
[
[1, 2],
[2, 1],
[7, 3],
[5, 1]
]
Explanation
Once we reduce the numbers they become [[2, 1], [2, 1], [7, 3], [7, 3], [5, 1], [1, 2]].
The result then comes from deduping and sorting by value.
import java.util.*;
class Solution {
public int[][] solve(int[][] fractions) {
Set<int[]> set = new TreeSet<>(
(fraction1,
fraction2) > (fraction1[0] * fraction2[1])  (fraction2[0] * fraction1[1]));
for (int[] fraction : fractions) {
int a = fraction[0], b = fraction[1];
int gcd = gcd(Math.max(Math.abs(a), Math.abs(b)), Math.min(Math.abs(a), Math.abs(b)));
int[] result = new int[] {a / gcd, b / gcd};
set.add(result);
}
int[][] ans = new int[set.size()][2];
int index = 0;
for (int[] answer : set) {
ans[index++] = answer;
}
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
Discussion (0)