136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

136. Одно число

Задан массив целых чисел, в котором каждое число встречается дважды кроме одного. Найдите это одно число.

Ваш алгоритм должен иметь линейную временную сложность и не использовать дополнительную память.

// C++

class Solution {

public:

int singleNumber(vector<int>& nums) {

}

};

// Java

public class Solution {

public int singleNumber(int[] nums) {

}

}

SOLUTION

sequences

Algorithm analysis

Make a xor operation of all elements in array. The result of xor operation equals to the number that appears once in array.

РЕШЕНИЕ

последовательности

Анализ алгоритма

Совершим над всеми числами массива оперцию xor. Результат ее выполнения равен искомому числу.

Реализация алгоритма

class Solution

{

public:

int singleNumber(vector<int>& nums)

{

int res = 0;

for(int i = 0; i < nums.size(); i++)

res ^= nums[i];

return res;

}

};

Java реализация

public class Solution

{

public int singleNumber(int[] nums)

{

int res = 0;

for(int i = 0; i < nums.length; i++)

res ^= nums[i];

return res;

}

}