Мне нужно найти недостающее число в последовательности, не отсортированной. Эта последовательность хранится в объекте String. Например, в этой последовательности: 3 1 6 5 2
недостающее число - 4
. Между каждым номером есть \n
. Я должен сделать это, не используя структуры как Array, Dictionary, Lists и т. Д., Потому что мне нужно иметь сложность O (1). На входе я получаю также максимальное число последовательности (в последовательности примеров, я получаю номер 6) Любая идея?Найти недостающее число в последовательности, не отсортированной
ответ
МЕТОД 1 (Использовать формулу сумма) Алгоритм:
- Получить сумму чисел всего = п * (п + 1)/2 ----------- O (1)
2 Вычесть все числа от суммы и вы получите недостающее число
void ans(int total){ ///O(1)
big_total = (n+1)*(n+2)/2; // n+1 because 1 number is missing
return (big_total-total);
}
input_array()
{
int n,total=0,i;
cout<<"enter no of element";
cin>>n;
for(i=0;i<n;i++)
{
cin>>arr[i];
total+=arr[i];
}
cout<<ans(total);
}
не должно быть вашим большим итогом n * ((n + 1)/2) ? –
позволяет сказать 'n = 4', чем' arr [] = {1,3,4,5} ', чем мы используем' n + 1', потому что отсутствует одно число, поэтому общее число составляет '5' –
Да, но вопрос говорит, что не разрешено использовать массив и максимальное число. Поэтому максимальное число должно быть n и не нужно для массива. –
Покажите нам свой код или как далеко вы пробовали эту проблему. – Gatusko
Сложность O (1) возможна только с верхним пределом длины последовательности. В противном случае вы застряли с O (n * log n) (то есть сначала сортируйте и ищите недостающее число). Или, может быть, O (n), если вы не заботитесь о пространстве. – Ctx
Сравните сумму последовательности с суммой целых чисел между значениями min и max. –