剑指 Offer 03. 数组中重复的数字

剑指 Offer 03. 数组中重复的数字

难度：简单 题目描述 解题思路

1、简单哈希

因为数组范围确定，所以可以用一个很简单的数组来代替哈希表

public int findRepeatNumber(int[] nums) { int n = nums.length; int[] count = new int[n]; for (int i = 0; i < nums.length; i++) { if(count[nums[i]] != 0) { return nums[i]; } count[nums[i]]++; } return -1; }

2ms

2、原地哈希

如果没有不能修改本来数组的要求，这应该是最优解了。 根据鸽笼原理，有重复的数字，那肯定有有数字要占别人的位置

/* * 剑指 Offer 03. 数组中重复的数字 * 2020/7/2 原地哈希算法 */ public int findRepeatNumber(int[] nums) { for (int i = 0; i < nums.length; i++) { while(nums[i] != i) { //如果当前下标和元素不匹配 if(nums[nums[i]] == nums[i]) { //如果这个数字已经出现在正确的位置，说明重复了 return nums[i]; } int temp = nums[nums[i]]; nums[nums[i]] = nums[i]; nums[i] = temp; } } return -1; }