剑指 offer 数组中重复的数字

算法名称:数组中重复的数字

题目内容:

在一个长度为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

}

本题考点:

  • 考察面试者对一维数组的理解与编程能力。一维数组在内存中占据连续的空间,因此我们可以根据下标定位对应的元素。

发表评论

电子邮件地址不会被公开。 必填项已用*标注