leetcode-面试题03.数组中重复的数字

1. 暴力枚举
  简单的方法便是双层循环嵌套遍历数组，直到找到第一个出现重复的数字则输出。
  时间复杂度是O(n²)，空间复杂度是O(1)。代码略。

2. 排序
  遍历数组前完全可以先对数组进行排序，从而可降低时间复杂度，然后遍历数组，相邻项存在相等的情况则输出。java.util.Arrays提供了Arrays.sort()方法可以对数组进行升序排序，源码中该方法提供的是快速排序算法.
  时间复杂度O(nlogn)，空间复杂度是O(1)

public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);
// 注意条件表达式是i<nums.length-1
for(int i=0;i<nums.length-1;i++) {
if(nums[i]==nums[i+1])
return nums[i];
}
return -1;
}

3. 哈希表
  java中实现哈希表数据结构的类有HashMap、HashSet，可选用。

• HashMap和HashSet、Hashtable的区别
• Class HashSet<E>
• Class HashMap<K,V>

//HashMap
public int findRepeatNumber(int[] nums) {
HashMap map
= new HashMap();
for(int i : nums) {
if(map.containsValue(nums[i]))
{
return nums[i];
}
else map.put(i, nums[i]);
}
return -1;
}
//HashSet
public int findRepeatNumber(int[] nums) {
HashSet set
= new HashSet();
for(int i : nums) {
if(!set.add(nums[i]))
return nums[i];
}
return -1;
}

因为对java类的不熟悉（想到了contains方法，但不记得哪个类有此方法），所以没想到用set集合等，这里用了数组下标和数组元素的对应关系，将下标看作key，元素看作value。

public int findRepeatNumber(int[] nums) {
int l = nums.length;
int[] nums2 = new int[l];
for(int i=0;i<l;i++) {
//初始化数组为-1
nums2[i] = -1;
}
for(int i=0;i<l;i++) {
int j = nums[i];
if(nums2[j]==-1) {
nums2[j]=j;
}
else {
return j;
}
}
return -1;
}

以上方法的时间复杂度是O(n)，空间复杂度是O(n)
4. 改变数组，比较-交换
  因为数组下标和数组元素的对应关系，可以从头遍历数组，判断下标为i的的数value是否等于i，若等于，则扫描下一个数；若不等，则比较下标为value的数与value值，若相等，则找到了重复数字，输出即可，若不等，则将value与nums[value]交换，使得下标与元素对应。

  时间复杂度是O(n)，空间复杂度是O(1)。

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

最后

以上就是火星上玉米为你收集整理的leetcode-面试题03.数组中重复的数字的全部内容，希望文章能够帮你解决leetcode-面试题03.数组中重复的数字所遇到的程序开发问题。

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