做图片详情网站,做电商网站一般需要什么流程,二级域名是什么意思,北京如何做网站#x1f604;#x1f60a;#x1f606;#x1f603;#x1f604;#x1f60a;#x1f606;#x1f603;
开始cpp刷题之旅。
目标#xff1a;执行用时击败90%以上使用 C 的用户。 136. 只出现一次的数字
给你一个 非空 整数数组 nums #xff0c;除了某个元素只出现…
开始cpp刷题之旅。
目标执行用时击败90%以上使用 C 的用户。 136. 只出现一次的数字
给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。
示例 1
输入nums [2,2,1] 输出1 示例 2
输入nums [4,1,2,1,2] 输出4 示例 3
输入nums [1] 输出1
解题
这题看上去简单但是考虑到效率性还是有很多讲究的。
有几种比较简单的方法
法一
循环遍历数组直接使用find()查找另一个如果没有找到说明这个数就是题目需要的那个直接返回有就继续。 但是这样效率会差点你之前找的数下一次可能还要继续查找一次浪费效率。
法二
先对数组进行排序。循环遍历排序后的数组如果当前数和下一个数相等则说明有重复的i1; 当前数如果和下一个不等就直接返回。 这样可以避免重复查找的问题但是会涉及到排序。
法三
使用异或。 一个数与本身异或等于00与其他数异或等于那个数这句话很重要。
这样只要遍历一次即可也不用考虑排序的问题最适合这道题了。
class Solution {
public:int singleNumber(vectorint nums) {int res0;for(int i:nums)res^i; return res;}
};直接返回最后的结果肯定就是那个单独出现的数这个解法很巧妙。
看下提交记录
