剑指 offer 数组中重复的数字
2020-06-07 本文已影响0人
快乐的工程师
算法名称：数组中重复的数字
题目内容：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
解题思路：
(1) 一个简单的思路是先将数组排序，然后从头开始寻找重复数字。排序的时间复杂度为O(nlogn)；
(2) 利用hash表存储元素，若表中存在元素则找到重复数字。Hash查询时间仅用O(1)，算法时间复杂度为O(n)，但是需要一个哈希表，空间复杂度为O(n)；
(3) 利用元素数字都在0到n-1的范围内的特点，若不存在重复数字，则排序后的数字就在与其相同的索引值的位置，即数字i在第i个位置。遍历的过程中寻找位置和元素不相同的值，并进行交换排序。时间复杂度O(n)，空间复杂度O(1)。
实例代码：
- Java版
class Solution {
public int findRepeatNumber(int[] nums) {
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
for (int i = 0; i \< nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
return nums[i];
}
}
return 0;
}
}
- Golang版
func findRepeatNumber(nums []int) int {
if len(nums) == 0 {
return 0
}
sort.Ints(nums)
for i := 0; i \< len(nums)-1; i++ {
if nums[i] == nums[i+1] {
return nums[i]
}
}
return 0
}
本题考点：
- 考察面试者对一维数组的理解与编程能力。一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应的元素。
