弹幕做的视频网站,苏州建站免费模板,有一个箭头的做网站的软件,网页平面设计是什么个人主页#xff1a; 进朱者赤 阿里非典型程序员一枚 #xff0c;记录平平无奇程序员在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法#xff08;公众号同名#xff09; 目录 题目描述思路及实现方式一#xff1a;使用异或运算#xff08;推荐#xff09;思… 个人主页 进朱者赤 阿里非典型程序员一枚 记录平平无奇程序员在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法公众号同名 目录 题目描述思路及实现方式一使用异或运算推荐思路代码实现Java版本C语言版本Python3版本 复杂度分析 方式二哈希表思路代码实现Java版本C语言版本Python3版本 复杂度分析 总结相似题目其他小知识几个有趣的位操作1. 利用或操作 | 和空格将英文字符转换为小写2. 利用与操作 和下划线将英文字符转换为大写3. 利用异或操作 ^ 和空格进行英文字符大小写互换4. 加一5. 减一其他 标签(题目类型)位运算
题目描述
136. 只出现一次的数字
给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。示例 1 输入nums [2,2,1]
输出1
示例 2 输入nums [4,1,2,1,2]
输出4
示例 3 输入nums [1]
输出1
提示1 nums.length 3 * 104
-3 * 104 nums[i] 3 * 104
除了某个元素只出现一次以外其余每个元素均出现两次。原题 LeetCode: LeetCode 136 力扣 : 力扣 136
思路及实现
方式一使用异或运算推荐
思路
利用异或运算的性质任何数和0异或等于它本身任何数和其自身异或等于0异或运算满足交换律和结合律。因此我们可以将数组中的所有数字进行异或运算出现两次的数字会相互抵消最终剩下的就是只出现一次的数字。
以[4,1,3,4,3]以例 面试官最期待的解法思路考察计算机基础知识
代码实现
Java版本
class Solution {public int singleNumber(int[] nums) {int x 0;for (int num : nums) // 1. 遍历 nums 执行异或运算x ^ num;return x; // 2. 返回出现一次的数字 x}
} 说明 通过遍历数组中的每个数字并使用异或运算将结果保存在result变量中最终返回result即可。 C语言版本
#include stdio.hint singleNumber(int* nums, int numsSize) {int x 0;for (int i 0; i numsSize; i) { // 1. 遍历 nums 执行异或运算x ^ nums[i];}return x; // 2. 返回出现一次的数字 x
} 说明 使用for循环遍历数组将每个元素与result进行异或运算并更新result的值。 Python3版本
class Solution:def singleNumber(self, nums: List[int]) - List[int]:x 0for num in nums: # 1. 遍历 nums 执行异或运算x ^ num return x; # 2. 返回出现一次的数字 x 说明 Python中的实现与Java和C类似使用for循环遍历数组并通过异或运算找出只出现一次的数字。 复杂度分析
时间复杂度O(n)其中 n 是数组 nums 的长度。这是因为我们只需要遍历一次数组对每个元素进行一次异或操作。空间复杂度O(1)因为我们只使用了常数个额外的变量来存储中间结果与输入数组的大小无关。
方式二哈希表
思路
使用哈希表记录每个数字出现的次数最后找到出现次数为 1 的数字即为答案。
下面以HashMap为例HashSet也是可以的
代码实现
Java版本
class Solution {public int singleNumber(int[] nums) {MapInteger, Integer counts new HashMap();for (int num : nums) {counts.put(num, counts.getOrDefault(num, 0) 1); // 统计每个数字出现的次数}for (int num : counts.keySet()) {if (counts.get(num) 1) {return num; // 返回出现次数为 1 的数字}}return -1; //理论上不会到达这里}
}说明 创建一个哈希表 counts用于存储每个数字出现的次数。 遍历数组 nums统计每个数字出现的次数并更新到 counts 中。 遍历 counts找到出现次数为 1 的数字并返回。 C语言版本
#include stdio.h
#include stdlib.h// 假设数字范围在 0 到 10000 之间可以使用数组模拟哈希表
int singleNumber(int* nums, int numsSize) {int counts[10001] {0};for (int i 0; i numsSize; i) {counts[nums[i]]; // 统计每个数字出现的次数}for (int i 0; i 10001; i) {if (counts[i] 1) {return i; // 返回出现次数为 1 的数字}}return -1; //理论上不会到达这里
} 说明 使用数组模拟哈希表假设数字范围在 0 到 10000 之间。逻辑与 Java 版本类似。 Python3版本 class Solution:def singleNumber(self, nums: List[int]) - int:counts {}for num in nums:counts[num] counts.get(num, 0) 1 # 统计每个数字出现的次数for num, count in counts.items():if count 1:return num # 返回出现次数为 1 的数字return -1 #理论上不会到达这里 说明 复杂度分析
时间复杂度O(n)其中 n 是数组 nums 的长度。需要遍历一次数组进行计数以及遍历哈希表查找出现次数为 1 的数字。空间复杂度O(n)最坏情况下哈希表需要存储所有不同的数字空间复杂度为 O(n)。
总结
方式优点缺点时间复杂度空间复杂度其他异或运算代码简洁效率高不直观需要理解异或运算的特性O(n)O(1)适用于数字类型的题目哈希表思路直观易于理解空间复杂度较高需要额外的存储空间O(n)O(n)适用于各种数据类型的题目
相似题目
相似题目难度链接两个数组的交集简单leetcode-349数组中数字出现的次数简单leetcode-136只出现一次的数字 II中等leetcode-137找出数组中消失的数字简单leetcode-448数组中重复的数据简单leetcode-287
其他小知识
几个有趣的位操作
1. 利用或操作 | 和空格将英文字符转换为小写
(a | ) a
(A | ) a
2. 利用与操作 和下划线将英文字符转换为大写
(b _) B
(B _) B3. 利用异或操作 ^ 和空格进行英文字符大小写互换
(d ^ ) D
(D ^ ) d
说明 以上操作能够产生奇特效果的原因在于 ASCII 编码。ASCII 字符其实就是数字恰巧空格和下划线对应的数字通过位运算就能改变大小写。
eg: 以1. 利用或操作 | 和空格将英文字符转换为小写为例 字符 ‘A’ 的 ASCII 值是 65。 字符 ’ 空格的 ASCII 值是 32。 按位或操作是这样的 65 (二进制: 01000001) |32 (二进制: 00100000) 97 (二进制: 01100001) 得到的结果 97 是字符 ‘a’ 的 ASCII 值。 因此‘A’ | ’ ’ 的结果是字符 ‘a’。 注意: 这种操作通常不用于处理文本或字符串因为它依赖于字符的特定 ASCII 编码并且可能会导致非预期的结果或难以理解的代码。在大多数情况下处理字符和字符串时应使用语言提供的字符串处理函数和操作符而不是按位操作符。
4. 加一
int n 1;
n -~n;
// 现在 n 25. 减一
int n 2;
n ~-n;
// 现在 n 1其他
技巧技巧描述示例技巧1判断奇偶性使用与运算符和1进行位与运算结果为0则为偶数结果为1则为奇数int num 5;boolean isEven (num 1) 0;技巧2交换两个数使用异或运算符^进行交换两个数不需要额外的临时变量int a 3, b 5;a a ^ b;b a ^ b;a a ^ b;技巧3取反操作使用取反运算符~进行取反操作int num 7;int result ~num;技巧4清除最低位的1使用减一后进行与运算操作int num 12;int result num (num - 1);技巧5判断是否为2的幂通过n与n-1进行与运算结果为0则是2的幂int num 16;boolean isPowerOfTwo (num (num - 1)) 0;技巧6位移操作左移和右移操作进行位移运算int num 8;int leftShifted num 1;int rightShifted num 1;技巧7判断两个数是否异号通过异或运算符^进行判断两数的符号位是否相同int x -1, y 2;boolean isOpposite ((x ^ y) 0);
说明技巧7 判断两个数是否异号 利用的是补码编码的符号位。整数编码最高位是符号位负数的符号位是 1非负数的符号位是 0再借助异或的特性可以判断出两个数字是否异号。
当然如果不用位运算来判断是否异号需要使用 if else 分支还挺麻烦的。你可能想利用乘积来判断两个数是否异号但是这种处理方式容易造成整型溢出从而出现错误。 欢迎一键三连(关注点赞收藏)技术的路上一起加油代码改变世界 关于我阿里非典型程序员一枚 记录平平无奇程序员在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法公众号同名 ⬇️⬇️欢迎关注下面的公众号进朱者赤认识不一样的技术人。⬇️
