leetcode 287. Find the Duplicate Number 寻找重复数 (中等)
LeetCode The number 重复 Find 寻找 中等 Duplicate
2023-09-11 14:22:52 时间
一、题目大意
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1:
输入:nums = [1,3,4,2,2]
输出:2
示例 2:
输入:nums = [3,1,3,4,2]
输出:3
提示:
- 1 <= n <= 105
- nums.length == n + 1
- 1 <= nums[i] <= n
- nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次
进阶:
-
如何证明 nums 中至少存在一个重复的数字?
-
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、解题思路
这道题给我们n+1个数,所有的数都在[1, n]区域内,首先让证明必定会有一个重复数,题目要求不能改变原数组,即不能给原数组排序,又不能用多余空间,那么hash的就不用考虑了,又要求时间小于O(n^2),只能考虑用二分搜索法了,在区间[1, n]中搜索,首先求出中点mid,然后遍历整个数组,统计所有小于等于mid的数的个数,如果个数小于等于mid,则说明重复值在[mid+1, n]之间,反之,重复值在[1, mid-1]之间,然后依次类推,直到搜索完成,此时的low就是我们要求的重复值。
三、解题方法
3.1 Java实现
public class Solution {
public int findDuplicate(int[] nums) {
int left = 1;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
int cnt = 0;
for (int num : nums) {
cnt += (num <= mid) ? 1 : 0;
}
if (cnt <= mid) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
}
四、总结小记
- 2022/10/25 旦行好事,莫问前程
相关文章
- 记录一次在生成数据库服务器上出现The timeout period elapsed prior to completion of the operation or the server is not responding.和Exception has been thrown by the target of an invocation的解决办法
- SQLBackupAndFTP The server principal "NT AUTHORITYSYSTEM" is not able to access the database "xxxx"
- Java实现 LeetCode 767 重构字符串(ASCII的转换)
- Java实现 LeetCode 669 修剪二叉搜索树(遍历树)
- Java实现 LeetCode 611 有效三角形的个数(双指针)
- Java实现 LeetCode 470 用 Rand7() 实现 Rand10()
- Caused by: org.xml.sax.SAXParseException: The reference to entity "characterEncoding" must end with the ';' delimiter.
- [RxJS 6] The Catch and Rethrow RxJs Error Handling Strategy and the finalize Operator
- 【数组&双指针】LeetCode 76. 最小覆盖子串【困难】
- leetcode 124. 二叉树中的最大路径和
- 【Codeforces Round #427 (Div. 2) B】The number on the board
- The size of tensor a (4) must match the size of tensor b (3) at non-singleton dimension 0
- Leetcode 343. 整数拆分
- Leetcode 202. 快乐数(一点都不快乐)
- Caused by: org.xml.sax.SAXParseException; systemId: file:/home/hadoop/hive-0.12.0/conf/hive-site.xml; lineNumber: 5; columnNumber: 2; The markup in the document following the root element must be well
- HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树
- Warning:detected "cgroupfs" as the Docker cgroup driver. The recommended driver is "systemd".
- 编译webrtc报错:ERROR: The installation of the Chrome OS default fonts failed.
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【LeetCode】剑指 Offer II 049. 从根节点到叶节点的路径数字之和
- 【异常】FlinkException: The module flink-runtime-web could not be found in the class path