[Leetcode] 136. Single Number 解题报告

xiaoxiao2021-02-27  155

题目:

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

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

思路:

这道题目思路对了就不难,否则解起来就比较痛苦了。它考查的其实是位操作。位操作中的异或有一个特点,就是两个相同的数异或之后变成0,而0和某个数异或的结果会是这个数本身。利用这个性质,我们只要遍历数组中的所有数,将它们都进行异或运算,就得到了最终要求的结果。算法的时间复杂度是O(n),空间复杂度是O(1)。

代码:

class Solution { public: int singleNumber(vector<int>& nums) { if (nums.size() == 0) { return 0; } int value = nums[0]; for (int i = 1; i < nums.size(); ++i) { value = value ^ nums[i]; } return value; } };

转载请注明原文地址: https://www.6miu.com/read-12891.html

最新回复(0)