一个主机多个网站,介绍一个做美食的网站,建筑培训网考题答案,网站改版有什么影响题目描述#xff1a;
给你一个 非空 整数数组 nums #xff0c;除了某个元素只出现一次以外#xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题#xff0c;且该算法只使用常量额外空间。示例 1 #xff…题目描述
给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。示例 1 输入nums [2,2,1]
输出1
示例 2 输入nums [4,1,2,1,2]
输出4
示例 3 输入nums [1]
输出1
算法一hash表
思路
用hash表记录数出现的次数之后遍历一次查找次数为1的数输出
易错点nums[i]可能出现负数但arr下标不能为负数故要进行讨论
代码实现
int singleNumber(int* nums, int numsSize) {int arr[200000]{0};//hash表int i;for(i0;inumsSize;i){if(nums[i]0) arr[nums[i]10000];//负数下标让负数向右偏移10000(防止覆盖原正数)else arr[nums[i]];}for(i0;inumsSize;i){//分正负讨论if(nums[i]0){//只出现一次--跳出循环if(arr[nums[i]10000]1) break;}else{if(arr[nums[i]]1) break;}}return nums[i];
}
算法二位运算
思路
0和任何数异或运算得到那个数本身
相同的两个数做异或运算得0
偶次会消掉只留下奇次
代码实现
int singleNumber(int* nums, int numsSize) {int ret0;for(int i0;inumsSize;i) ret^nums[i];return ret;
}
