新闻详情

新闻详情

首页 / 资讯中心 / 详情

【技巧】【简单/中等】只出现一次的数字/多数元素/颜色分类/下一个排列/寻找重复数

发布时间:2026/11/18 14:07:19来源:尧图网络
【技巧】【简单/中等】只出现一次的数字/多数元素/颜色分类/下一个排列/寻找重复数
1.只出现一次的数字原题链接位运算 XOR异或自己和自己异或等于 0。a ^ a 0任何数字和 0 异或等于自己。a ^ 0 a异或满足交换律和结合律。a ^ b b ^ a(a ^ b) ^ c a ^ (b ^ c)例如[4,1,2,1,2]把所有数字异或4 ^ 1 ^ 2 ^ 1 ^ 2 4 ^ (1 ^ 1) ^ (2 ^ 2) 4publicintsingleNumber(int[]nums){intres0;for(intnum:nums){res^num;}returnres;}2.多数元素原题链接摩尔投票算法nums [2,2,1,1,1,2,2] 统计结果2 出现 4 次、1 出现 3 次。不同数字两两抵消2和1 相互抵消最终剩下2维护两个变量candidate // 当前候选数字count // 当前候选数字的票数count 0说明之前的候选人已经被抵消。重新选择当前数字。当前数字等于 candidate 票数增加当前数字不等于 candidate 票数减小。publicintmajorityElement(int[]nums){intcandidate0;intcount0;for(intnum:nums){if(count0){candidatenum;}if(numcandidate){count;}else{count--;}}returncandidate;}3.颜色分类原题链接三指针一次遍历,最终得到的标签范围如下[0, p0)全是0[p0, i)全是1[i, p2]待处理区域(p2, n-1]全是2- p0表示 0 区域的右边界初始为 0 - i当前遍历位置初始为 0 - p2表示 2 区域的左边界初始为 n - 1如果 nums[i] 0和 p0 位置交换p0i如果 nums[i] 1直接 i如果 nums[i] 2和 p2 位置交换p2–注意i 不增加因为从后面换过来的数字还没有检查nums[2,1,2,1,0,0]初始i0、p00,p25nums[0]2,交换nums[0]和nums[5],p2--[0,1,2,1,0,2]nums[0]0,交换nums[0]和nums[0],p0,i[0,1,2,1,0,2]nums[1]1,直接i[0,1,2,1,0,2]nums[2]2,交换nums[2]和nums[4],p2--[0,1,0,1,2,2]nums[2]0,交换nums[0]和nums[1],p0,i[0,0,1,1,2,2]nums[3]1,i[0,0,1,1,2,2]i4p23循环结束publicvoidsortColors(int[]nums){intnnums.length;intp00;// 0 区域右边界inti0;// 当前遍历位置intp2n-1;// 2 区域左边界while(ip2){if(nums[i]0){swap(nums,i,p0);p0;i;}elseif(nums[i]1){i;}else{// nums[i] 2swap(nums,i,p2);p2--;// 这里不能 i因为换过来的元素还没判断}}}privatevoidswap(int[]nums,inti,intj){inttempnums[i];nums[i]nums[j];nums[j]temp;}4.下一个排列原题链接找到字典序中刚好比当前排列大的最小排列[1,2,3]-[1,3,2][1,3,2]-[2,1,3][3,2,1]-[1,2,3]//从右往左看如果数组一直是降序的,例如[3,2,1],没有下一个更大的排列了。所以我们要从右往左找到第一个升序的位置[1,2,3]从右向左寻找最右侧的第一个升序位置比如数组[1,3,2,5,4]需要进行替换的位置是2因为对于2来说它后面有比自己较大的数字应从中选择一个最小的来进行替换剩余的数进行升序排列。如果此时是[1,3,2,4,5]这样第一个升序就是4这个位置寻找到后此时右侧位置上全是逐渐降序的数字列需要找到比 a[i] 大的最小数字然后进行交换交换后右半部分还是递减的然后将右半部分进行翻转从小到大nums[1,3,2,5,4]寻找到最右侧递减的位置为2,i2》寻找要交换的数字位置 所以 i2nums[i]2》寻找交换数字的位置 在 i 后面寻找第一个比 nums[i]大的数字13254↑42所以 j4nums[j]4》交换 nums[i]和 nums[j]13254↘ ↙13452》反转 i 后面的数组[1,3,4,2,5]publicvoidnextPermutation(int[]nums){//从右向左寻找第一个非递减的元素位置intinums.length-2;for(;i0;i--){if(nums[i]nums[i1]){break;}}//如果位置为-1,就直接翻转整个数组if(i!-1){//从右向左寻找第一个大于nums[i]的元素位置for(intjnums.length-1;ji;j--){if(nums[j]nums[i]){swap(nums,i,j);break;}}}//将i1到nums.length-1的元素反转reverse(nums,i1,nums.length-1);}privatevoidswap(int[]nums,inti,intj){inttempnums[i];nums[i]nums[j];nums[j]temp;}privatevoidreverse(int[]nums,intleft,intright){while(leftright){swap(nums,left,right);left;right--;}}5.寻找重复数原题链接直接用HashSet也可以但是要求只用常量级 O(1) 的额外空间publicintfindDuplicate(int[]nums){SetIntegersetnewHashSet();for(intnum:nums){if(set.contains(num)){returnnum;}set.add(num);}return-1;}快慢指针把数组看成一个链表重复数字就是链表的环入口。nums[1,3,4,2,2]index-value index:01234value:134220-1-3-2-4-2-4-... 最终重复数字就是环的入口 因为必然出现两个位置指向同一个节点例如 nums[3]2nums[4]2表示3-2、4-2即为环节点publicintfindDuplicate(int[]nums){//快慢指针intslownums[0];intfastnums[0];// 第一次快慢指针找相遇点do{slownums[slow];fastnums[nums[fast]];}while(slow!fast);// 第二次寻找入口// 从头开始每次走一步直到再次相遇slownums[0];while(slow!fast){slownums[slow];fastnums[fast];}returnslow;}
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/18 21:21:17

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/18 14:20:46

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/18 20:01:42

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/18 11:04:06

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/18 15:55:22

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/18 21:21:16

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉