剑指Offer 面试题03. 数组中重复的数字（Java代码）

前往LeetCode做题

题目描述

长度为 n的数组中，数字介于 0~n-1 之间。数组中的某些数字是重复的，只要找出其中的一个重复的数字即可。

输入输出样例

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

题解

（法一）使用hashset集合查重：

• Java中HashSet类的底层实现是HashMap
• HashMap的增删元素和查找元素的时间复杂度都是O(1)

这种解法需要额外的O(N)空间

class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
for(int num:nums){
// 如果HashSet中包含该数字，即该数字重复
if(set.contains(num)) return num;
set.add(num);
}
return -1;
}
}

（法二）将数组排序：

• 将数组进行排序
• 再次遍历数组，如果发现相邻的两个数字相等，说明该数字是重复的

class Solution {
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);
for(int i=1; i<nums.length; i++){
if(nums[i] == nums[i-1]) return nums[i];
}
return -1;
}
}

本来是手写排序代码的（写了个冒泡），后面测试用例一跑。用时 1114 ms。
还是使用Arrays吧，它内部的对于数组的判断机制非常完善了，用时 3 ms。

（法三）数组下标定位法：
题目说了，数组长度n，元素介于0-n-1之间。

• 这种情况下的 数组可以看作是一个 哈希表
• 如果没有重复元素的话，数组的元素和数组的下标是一一对应的

class Solution {
public int findRepeatNumber(int[] nums) {
for(int i=0;i<nums.length; i++){
// 如果当前下标不是值，那么将该下标处的值换到指定位置
if(nums[i] != i){
int temp = nums[i];
// 如果需要交换的位置已经有值了，说明重复
if(nums[temp] == temp) return temp;
// 否则交换值
swap(nums, i, temp);
}
}
return -1;
}
public void swap(int[] nums, int i1, int i2){
int temp = nums[i1];
nums[i1] = nums[i2];
nums[i2] = temp;
}
}

最后

以上就是笑点低煎饼为你收集整理的剑指Offer 面试题03. 数组中重复的数字（Java代码）的全部内容，希望文章能够帮你解决剑指Offer 面试题03. 数组中重复的数字（Java代码）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。