Given an array containing n distinct numbers taken from 0, 1, 2,
..., n, find the one that is missing
from the array.
For example, given nums = [0, 1, 3] return 2.
Задан массив, содержащий n различных чисел из промежутка 0,1 , 2,
..., n. Найдите пропущенное число.
Например, если nums = [0, 1, 3], то возвращаемое
значение равно 2.
// C++
class Solution {
public:
int missingNumber(vector<int>&
nums) {
}
};
// Java
public class
Solution {
public int
missingNumber(int[] nums) {
}
}
последовательности
Первое решение. Вычислим сумму всех чисел
от 0 до n. Затем вычтем из полученной
суммы все числа из заданного массива. Полученное число – искомое пропущенное.
Второе решение. Вычислим xor всех чисел от 0 до n. Затем последовательно применим
операцию xor к результату и всем
числам из заданного массива. Получим искомое пропущенное число.
Реализация алгоритма
class Solution
{
public:
int missingNumber(vector<int>&
nums)
{
int i, res = nums.size();
for(i = 0; i < nums.size(); i++)
res ^= nums[i] ^
i;
return res;
}
};
Java реализация
public class Solution
{
public int
missingNumber(int[] nums)
{
int res = nums.length;
for(int i = 0; i <
nums.length; i++)
res ^= nums[i] ^
i;
return res;
}
}