LeetCode第287题,难度中等。
原题地址:https://leetcode-cn.com/problems/find-the-duplicate-number/
题目描述:
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
这个题目要求只能使用额外的O(1)的空间,时间复杂度小于O(n^2),所以不能使用位图的方式。但是存在其他的多种方式。
第一种:我认为是最简单粗暴的一种方式,时间复杂度最差情况下刚好是O(n^2),也就是循环遍历数组,分别比对每个元素,在数组中是否存在相同的元素,如果存在相同的元素,则立即返回。
第二种:先排序,排序之后,相同的元素必然处于相邻的位置,那么直接遍历一次即可(当然这个方法存在利用额外的空间,空间复杂度可能不是O(1))
第三种:利用Set集合,不过也很明显使用了额外空间。
中文官网题解:
https://leetcode-cn.com/problems/find-the-duplicate-number/solution/
个人题解:
public class Solution {
public int findDuplicate(int[] nums) {
for(int i = 0; i < nums.length; i++){
for(int j = i + 1; j < nums.length; j++){
if(nums[i] == nums[j])
return nums[i];
}
}
return 0;
}
}
结果:
这个是简单粗暴的方式的执行结果,可以很明显看到快的速度可以达到近乎0ms。