(1)找出数组中重复的数字
题目
在一个长度为n的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为7的数组 {2, 3, 1, 0, 2, 5, 3}
,那么对应的输出是重复的数字2或者3。
解法1[Java]:动态重排序加判断
把值为 i 的元素放到第 i 个位置上去,如果它和第 i 个位置上的元素值相等,那么可以判断这个元素是重复的。
1 | public class Solution { |
复杂度分析
时间复杂度为 $O(n)$。由于是直接对原数组进行操作,空间复杂度为 $O(1)$。
解法2[Java]:排序然后判断
解法3[Java]:使用Hash数据结构
总结
解法1只适合对数字型问题进行查找重复。解法2和解法3还可以用于对象的查找重复。
(2)不修改数组找出重复的数字
题目
在一个长度为n+1的数组里的所有数字都在1到n的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7},那么对应的输出是重复的数字2或者3。
解法1[C++]:数数判定
1 |
|