您的位置 首页 golang

剑指 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}

本题考点:

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

文章来源:智云一二三科技

文章标题:剑指 offer 数组中重复的数字

文章地址:https://www.zhihuclub.com/5196.shtml

关于作者: 智云科技

热门文章

网站地图