Leetcode讲解:剑指 Offer 03. 数组中重复的数字
2022/1/4 23:04:31
本文主要是介绍Leetcode讲解:剑指 Offer 03. 数组中重复的数字,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题:剑指 Offer 03. 数组中重复的数字
class Solution { /* public int findRepeatNumber(int[] nums) { Set<Integer> set = new HashSet<>(); for(int n : nums){ if(!set.add(n)){ return n; } } return 0; } */ public int findRepeatNumber(int[] nums) { int i = 0; while(i < nums.length){//注意:这里不能用for,因为不是所有情况i都+1,而是当第一个if成立时,i才+1。 if(nums[i] == i) { i++; continue; } if(nums[nums[i]] == nums[i]) return nums[i]; int temp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; } return -1; } }
核心算法:
由于题干中已知数组中的数都在0-n-1范围,利用这点可以在原地解决该题。
遍历中,第一次遇到数字 x 时,将其交换至索引 x 处;而当第二次遇到数字 x 时,一定有 nums[x] = x ,此时即可得到一组重复数字。
理解本题的测试用例:2,3,1,1
经验:
if(set.contains(n)){ return n; } else{ set.add(n); }
这段代码这样写更简洁:
if(!set.add(n)){ return n; }
知识点:
set.add(n)返回值是boolean,如果n已经在set中存在,返回false。
这篇关于Leetcode讲解:剑指 Offer 03. 数组中重复的数字的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20whatsapp webhook 回调的签名验证偶尔会失败是什么原因-icode9专业技术文章分享
- 2024-09-19Excel数据导出课程:初学者必备教程
- 2024-09-19Excel数据导入课程:新手入门指南
- 2024-09-19RBAC的权限管理入门教程
- 2024-09-19如何使用Svg Sprite Icon制作图标
- 2024-09-19uniapp 如何实现点赞后全局更新数据-icode9专业技术文章分享
- 2024-09-19云函数怎么运行wx-server-sdk-icode9专业技术文章分享
- 2024-09-19"dependencies": { "wx-server-sdk": "latest" },是什么意思-icode9专业技术文章分享
- 2024-09-16优化批处理流程:自定义BatchProcessorUtils的设计与应用
- 2024-09-15laravel collect游标批量插入的方法示例-icode9专业技术文章分享