如何做能上传视频网站,网站维护流程图,学做网站培训上海,设计院门户网站建设方案给你一个整数数组 nums #xff0c;除某个元素仅出现 一次 外#xff0c;其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
解法一
#include stdio.hint singleNumber(i…给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
解法一
#include stdio.hint singleNumber(int* nums, int numsSize) {unsigned int result 0;// 统计每个位上出现的次数for (int i 0; i 32; i) {int count 0;for (int j 0; j numsSize; j) {if ((nums[j] i) 1) {count;}}// 如果某位上出现的次数不能被 3 整除说明只出现一次的数在该位上为 1if (count % 3 ! 0) {result | (1u i);}}return (int)result; // 将结果强制转换为有符号整数类型
}int main() {int nums[] {2, 2, 3, 2};int numsSize sizeof(nums) / sizeof(nums[0]);printf(The single number is: %d\n, singleNumber(nums, numsSize));return 0;
}
tips: 后缀 u 表示将整数字面值常量指定为无符号整数。通常如果不带后缀的整数常量在程序中出现并且与无符号整数类型进行运算那么这个整数常量会被默认为有符号整数类型。因此当我们需要确保一个整数常量被视为无符号整数时可以在其后面添加 u 后缀来明确指定。
这里我们使用 (1u i) 来表示将无符号整数 1 左移 i 位确保不会出现符号位的影响。通过使用无符号整数我们可以避免在进行位运算时出现意外的结果尤其是涉及到位移操作时更需要注意这一点。
解法二
int singleNumber(int* nums, int numsSize) {int ones 0, twos 0;for (int i 0; i numsSize; i) {ones (ones ^ nums[i]) ~twos;twos (twos ^ nums[i]) ~ones;}return ones;
}
使用两个变量 ones 和 twos分别记录每个位上出现一次和两次的数字。通过适当的位运算更新这两个变量最终得到只出现一次的数字。
