LeetCode 136题：哈希表、排序与位运算解法详解-云帆数科

1. 问题背景与核心解法LeetCode 136题只出现一次的数字是算法入门经典题目给定一个非空整数数组其中某个元素只出现一次其余每个元素均出现两次要求找出那个只出现一次的数字。这道题看似简单却蕴含着多种解题思路特别适合用来理解不同算法思想的时间/空间复杂度差异。在实际工程中类似场景很常见——比如日志分析时找出异常请求ID或数据库去重时识别唯一记录。这道题的三种主流解法恰好代表了算法设计的典型思路暴力排序法时间复杂度O(nlogn)空间复杂度O(n)哈希表计数法时间复杂度O(n)空间复杂度O(n)位运算异或法时间复杂度O(n)空间复杂度O(1)2. C语言实现哈希表解法2.1 哈希表设计思路C标准库没有内置哈希表需要手动实现。考虑到题目限制数字范围在-3万到3万之间可以采用简化版的开放寻址法#define HASH_SIZE 60001 #define OFFSET 30000 int hash[HASH_SIZE]; void initHash() { memset(hash, 0, sizeof(hash)); } void insert(int num) { hash[num OFFSET]; } int findSingle(int nums[], int numsSize) { initHash(); for(int i 0; i numsSize; i) { insert(nums[i]); } for(int i 0; i numsSize; i) { if(hash[nums[i] OFFSET] 1) { return nums[i]; } } return -1; // 题目保证有解这里仅为容错 }注意这种实现利用了题目中数字范围有限的特性。若数字范围不限需改用链表法处理冲突或使用第三方库如uthash。2.2 复杂度分析时间复杂度O(n)两次线性遍历空间复杂度O(k)k为数字范围本例固定为600013. 排序解法实现与优化3.1 快速排序实现C语言标准库的qsort非常适合这种场景int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b); } int singleNumber(int* nums, int numsSize) { qsort(nums, numsSize, sizeof(int), compare); for(int i 0; i numsSize - 1; i 2) { if(nums[i] ! nums[i1]) { return nums[i]; } } return nums[numsSize - 1]; }3.2 边界情况处理当唯一数字出现在数组末尾时循环会遍历到倒数第二个元素因此需要单独返回最后一个元素。这是该解法最容易出错的地方。4. 位运算的魔法解法4.1 异或运算特性这是本题的最优解利用异或的三个性质a ^ 0 aa ^ a 0交换律a ^ b ^ a (a ^ a) ^ b 0 ^ b bint singleNumber(int* nums, int numsSize) { int result 0; for(int i 0; i numsSize; i) { result ^ nums[i]; } return result; }4.2 为什么这个方法有效假设数组是[4,1,2,1,2]初始0 ^ 4 44 ^ 1 55 ^ 2 77 ^ 1 66 ^ 2 4最终结果5. 三种解法的实测对比在LeetCode判题系统测试随机10万数据量解法运行时间内存消耗哈希表28ms7.5MB排序36ms7.2MB位运算12ms6.5MB实际工程中选择时还需考虑如果数字范围极大如64位整数哈希表解法需要调整如果内存极度受限位运算是最佳选择。6. 常见错误与调试技巧6.1 哈希表越界问题当数字为INT_MIN时num OFFSET可能下溢。防御性写法void insert(int num) { long index (long)num OFFSET; hash[index]; }6.2 排序解法的陷阱未处理末尾元素的情况// 错误写法 for(int i 0; i numsSize; i 2) { ... } // 当唯一数在末尾时会越界6.3 位运算的扩展思考如果题目改为两个唯一数解法会完全不同——需要先异或得到x^y再根据某位差异分组异或。7. 工程实践中的选择建议嵌入式环境优先位运算避免动态内存分配大数据处理哈希表法可分布式扩展已排序数据直接线性扫描无需预处理面试场景建议先给出哈希表解法再优化到位运算在C语言实际项目中如果频繁需要哈希表建议封装成泛型数据结构。这里给出一个简易模板typedef struct { int key; int val; } HashEntry; HashEntry* createHashTable(int size) { return (HashEntry*)calloc(size, sizeof(HashEntry)); } int hashFunc(int key, int size) { return (key % size size) % size; // 处理负数 }掌握这道题的多种解法不仅能应对面试更能培养对算法时空复杂度的敏感度。建议读者可以尝试用这三种方法解决LeetCode 137数字出现两次唯一数出现一次和260两个唯一数的变种问题。

企业数字化 ERP 产品动态

相关推荐

AI论文写作工具测评：提升科研效率的8款神器

1. 论文写作工具测评：为什么我们需要AI辅助？ 作为一名在高校混迹多年的科研狗，我深刻理解论文写作的痛苦。从开题报告到毕业论文，每个阶段都让人头秃。去年帮导师审阅研究生论文时，我发现一个有趣现象：那些… · 2026/11/2 10:18:16

光机组装应力控制：从锐缘到近曲率的四重接触范式

简介：《光机组装设计概论》是一本面向光学工程初学者与光机结构设计入门者的系统性参考资料，聚焦光学镜头组的结构设计、精密组装与工程实现，有效衔接光学设计与机械实现之间的关键断层。资源为单文件PDF，共1个6.74MB的高清中文文… · 2026/11/2 10:18:16

不只是工具：VoiceStudio语音制作流水线搭建指南

做语音内容这几年，我越来越觉得"VoiceStudio"这个词不该被理解成一个单纯的软件名，而应该被理解成一套完整的语音生产工作流。你可能也注意到了，最近一年搜"voicestudio"的人特别多，有人想找配音工具&#xf… · 2026/11/4 2:06:27

GD32E10x官方例程入门：从点灯到外设调试全流程

简介：这份GD32E10x系列官方例程面向使用兆易创新GD32E10x系列MCU的嵌入式开发者与初学者，基于ARM Cortex-M3内核，集合了从基础外设到通信、电机控制等场景的示例代码，可用于快速理解芯片用法并搭建工程。压缩包共935个文件&#x… · 2026/11/5 12:13:20

H110/B250主板BIOS魔改：CPU微码、ME与刷写校验全流程

简介：面向希望为 B150、B250、H110 等老主板扩展 Intel 8/9 代 CPU 兼容性的 DIY 玩家与装机爱好者，这份 BIOS 魔改工具包提供了一套较完整的固件修改辅助材料，适合具备一定硬件基础、了解刷写风险的用户在做好备份与稳定供电的前提下研究使用… · 2026/11/5 12:12:19

Stimulsoft Reports 2019.2.2 落地指南：老系统兼容与版本陷阱规避

简介：Stimulsoft Reports 2019.2.2 是一款面向.NET开发者的专业报表控件，适用于WinForms、ASP.NET及WPF平台，帮助开发者快速构建数据可视化报表与打印输出功能，尤其适合中高级C#工程师在企业级管理系统、BI看板或财务报表模块中集… · 2026/11/5 12:10:17

纯前端离散数据分析沙盒：分离度与趋势检验交互式实现

简介：本资源是一份面向统计学与数据科学专业本科生的离散数据分析学期项目实践包，聚焦逻辑回归中‘完美分离’这一典型建模难题，帮助学习者理解其成因、识别方法与多种稳健解决方案。资源共569个文件，含276个CSV格式模拟与实验数据… · 2026/11/5 12:09:17

服装CAD格式转换实战：AAMA DXF单位、图层映射与版片丢失排查

简介：面向服装CAD制版、放码与设计人员的一款格式转换工具，主要解决DXF与AAMA两类常见服装CAD数据在交换、导入导出时格式不兼容的问题，适合需要在不同CAD系统间迁移纸样、复用版片数据的初、中级使用者。资源包约2.79MB，压缩包内… · 2026/11/5 12:08:17

潍坊高纯氢氧化镁生产厂家怎么选：泽隆新材料靠谱商家测评排名

潍坊高纯氢氧化镁怎么选不踩坑：从产能、品控到定制能力，一篇讲透靠谱厂家的判断标准采购高纯氢氧化镁、阻燃级氢氧化镁，最怕的不是价格高，而是批次不稳、指标浮动、交期失控。尤其是做线缆料、橡胶制品、阻燃母粒的企业&#xff0… · 2026/11/5 12:07:17

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 10:27:59

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时，Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南：从原理到部署微调的全链路路线

提到大模型的系统性入门，我先说个结论：这事真不难，难的是资料太散、路线太多，今天这个框架明天那个工具，新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师，我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码，在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

LeetCode 136题：哈希表、排序与位运算解法详解

相关推荐

了解更多？预约专属演示