Casting — Мой алгоритм правильный, но некоторые результаты неверны? (C ++)
Таким образом, я взял этот урок практики под названием ‘PermMissingElement’ на www.codility.com, и вот мой код:
#include <iostream>
using namespace std;
int solution(vector<int> &A)
{
int N = A.size();
double Nf = double(N);
int n;
double missingf;
int missing;
double sumN1, sumN2;
int sum = 0;
double sumf;
double two = 2.0;
for (n = 0; n < N; n++)
{
sum = sum + A[n];
}
sumf = double(sum);
sumN1 = (Nf+double(1.0))/double(2.0);
sumN2 = sumN1*(Nf+double(2.0));
missingf = sumN2 - sumf;
missing = int(missingf);
return missing;
}
Теперь вот проблема. Мой алгоритм работает, но по какой-то причине я не могу понять, дает неправильные ответы на «большие» значения N. (N может быть максимум 100 000 в уроке).
Во всяком случае, я изначально написал программу, используя все целые числа, а затем понял, что из-за этого возможно переполнение, поэтому я изменил их на удвоения, но я все еще получаю неправильные ответы при больших значениях N … почему?
Спасибо
Решение
Двойные числа являются числами с плавающей запятой, что означает, что вы гарантированно потеряете точность, особенно для больших чисел. Вместо того, чтобы использовать int использовать другой интегральный тип, такой как long или же long long,
Стандарт C ++ не определяет точный размер для каждого типа, но int не менее 16 бит, long не менее 32 бит и long long не менее 64 бит
Проверьте этот ТАК вопрос для большего количества указателей: размер int, long и т. д.
Другие решения
Интересный подход у вас там, я решил ту же проблему в php, используя следующий алгоритм, интерпретируя каждое значение массива как индекс, а затем инвертируя значение. Позиция последнего значения> 0 является отсутствующей, и она все еще работает в O (n).
Таким образом вы избежите переполнения, добавляя большие числа, так как вам не нужно ничего добавлять.
error_reporting(0);
$s = count($A);
for ($i=0; $i<$s; $i++)
{
$n = abs($A[$i])-1;
$A[$n]*=(-1);
}
for ($i=0; $i<$s; $i++)
{
if ($A[$i]>0)
return $i+1;
}
return $s+1;