【经典算法】LeetCode 136:只出现一次的数字(Java/C/Python3实现含注释说明,Easy)

2024-04-16 17:36
文章标签 java leetcode 算法 实现 说明 经典 python3 注释 一次 数字 easy 136

本文主要是介绍【经典算法】LeetCode 136:只出现一次的数字(Java/C/Python3实现含注释说明,Easy)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

个人主页： 进朱者赤

阿里非典型程序员一枚 ，记录平平无奇程序员在大厂的打怪升级之路。 一起学习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.h>int 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) {Map<Integer, 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' & '_') = 'B'

3. 利用异或操作 ^ 和空格进行英文字符大小写互换

('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 = 2

5. 减一

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、大数据、数据结构算法（公众号同名）

⬇️⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️

这篇关于【经典算法】LeetCode 136:只出现一次的数字(Java/C/Python3实现含注释说明,Easy)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/909454。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
Zookeeper安装和配置说明

Zookeeper安装和配置说明

一、Zookeeper的搭建方式 Zookeeper安装方式有三种，单机模式和集群模式以及伪集群模式。 ■ 单机模式：Zookeeper只运行在一台服务器上，适合测试环境； ■ 伪集群模式：就是在一台物理机上运行多个Zookeeper 实例； ■ 集群模式：Zookeeper运行于一个集群上，适合生产环境，这个计算机集群被称为一个“集合体”（ensemble） Zookeeper通过复制来实现
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2