数组和矩阵(1)——Find the Duplicate Number
2024-08-27 23:05:39
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
- You must not modify the array (assume the array is read only). //不能排序
- You must use only constant, O(1) extra space. // 不能用哈希表
- Your runtime complexity should be less than O(n2). //不能暴力求解
- There is only one duplicate number in the array, but it could be repeated more than once.
https://segmentfault.com/a/1190000003817671#articleHeader4
考虑:
- 暴力求解,选择一个数,看有没有重复的;
- 哈希表
- 排序后遍历
- 二分法
- 设置快慢指针,映射找环法
public class Solution {
public int findDuplicate(int[] nums) { //映射找环
int n = nums.length - 1;
int pre = 0;
int last = 0;
do {
pre = nums[pre];
last = nums[nums[last]];
} while(nums[pre] != nums[last]);
last = 0;
while(nums[pre] != nums[last]) {
pre = nums[pre];
last = nums[last];
}
return nums[last];
}
}
最新文章
- Bootstrap之字体图标
- MJPhotoBrowser BUG修复
- Window 下 Qt5 使用QMediaplayer 进行视频播放 流播放问题
- iOS UIImageView用代码添加点击事件
- 定时组件quartz系列<;二>;quartz的集群原理
- 使用ckplayer搭建rtmp视频直播应用
- 小物件之radio单选列表
- 十年linux命令总结
- java 正则
- openwrt默认不开启wifi
- C++inserter
- BZOJ.5397.circular(随机化 贪心)
- 生成器函数yield
- 在ASP.NET Core 2.2 中创建 Web API并结合Swagger
- Integer’s Power HDU - 3208(容斥原理)
- 基本类型(2):oracle中有4个大对象(lobs)类型可用,分别是blob,clob,bfile,nclob。
- canvasJS
- 通过Application传递数据
- cocos2d-x JS 纯代码实现人物头像裁剪
- IE9 添加事件DOMContentLoaded,方法addEventListener
热门文章
- Sql Server两个数据库中有一张表的结构一样,怎么快速将一张表中的数据复制到另一个表中
- webstorm激活服务器地址
- centos下安装memcached并设置开机自动启动-两种方法
- JDBC_时间处理_Date_Time_Timestamp区别_随机日期生成
- JS 创建元素的三种方法
- α测试,Beta测试
- 编写高质量代码:Web前端开发修炼之道(一)
- Asp.Net 远程连接Oracle数据库
- bzoj1004 [HNOI2008]Cards Burnside定理+背包
- Laravel项目部署到Nginx服务器除了/目录,全飘404