Найти, сколько разных значений с плавающей точкой у меня в массиве
Для того, чтобы решить раздел из задачи, в которой мне дают N пары целых чисел Икс а также Y, Мне нужно найти сколько разных х / у здесь. (точное значение с десятичными знаками)
1.
Конечно, я мог бы просто перебрать все предыдущие пары и посмотреть, х / у значение произошло раньше, но это займет, я полагаю, (П ^ 2) / 2 время.
Я попытался использовать хэш-таблицу, но она не очень хорошо работает со значениями с плавающей точкой. Может быть, это будет работать с очень хорошей хэш-функцией.
2.
Учитывая, что Икс а также Y целые числа, я попробовал другой подход к проблеме:
- Вычислить наибольший общий делитель для каждой пары
- Делить Икс а также Y с GCD
-
Используйте матрицу m [max_value_of_x] [max_value_of_y] и сделайте это:
if ( m[x][y] ) { ; } else { m[x][y] = 1 ; cnt++ ; } -
Сделав это для всех пар, CNT должно быть количество различных значений с плавающей запятой.
Хотя, я думаю, это может занять приличное количество времени; это определенно не космический. В задаче на самом деле максимальное значение для Икс а также Y 1000, но выделенная память довольно мала.
Решение
Из решения MBo, используя набор:
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
Другие решения
Вы можете хранить пары x / y в списке или массиве и сортировать этот список с помощью функции сравнения, которая сравнивает x1 * y2 и x2 * y1 — обратите внимание, что все вычисления представлены в целых числах. После сортировки (NlogN) просмотрите список и посчитайте разные значения (сравнивая только соседей)
Другой подход может хранить все значения 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 ) ;
}