数组中重复的数字

• 🏠方法一：暴力求解
• 🏡方法二：哈希查找
• 🏘️方法三：原地置换

题目描述：💦

👉题目链接👈

🏠方法一：暴力求解

暴力求解的思路非常的直接：
遍历数组中的每个元素，然后在剩下的元素中寻找是否存在相同的元素。

代码如下👇

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

以上算法实现的复杂度分析：

• 时间复杂度是： O(n^2)
• 空间复杂度是 ：O(1)

细心的朋友应该会发现这道题目描述的最后对 n 做了一个限制，也就是：

     2 <= n <= 100000

那就是说，数据规模 n 有可能是 10 万级别的，如果时间复杂度是 O(n^2) 的话，那么数据规模就会变成 10 万的平方了，这个级别就高了，所以上面的代码的性能是非常差的。接下来我们来优化。

🏡方法二：哈希查找

在暴力解法中，我们先遍历每一个元素，然后再从其余的元素中查找这个元素是否存在，其实这里要的就是能高效的判断一个元素是否已经存在，我们可以使用哈希表，因为哈希表判断是否存在的时间复杂度是 O(1)。

代码如下👇

class Solution {public int findRepeatNumber(int[] nums) { Set<Integer> set = new HashSet<>();      //1.初始化一个哈希表 for (int i =0; i < nums.length; i++) {     if (set.contains(nums[i])) { //2.判断当前元素是否存在  return nums[i];      //3.存在的话，说明这个元素重复，直接返回     }     set.add(nums[i]);     //4.不存在的话，将当前元素放入哈希表中，方便后续的判断重复 } return -1;    }

以上算法实现的复杂度分析：

• 时间复杂度是：O(n)
• 空间复杂度是 ：O(n)

🏘️方法三：原地置换

这一种方法也是我们经常用到的，主要用于重复出现的数，缺失的数等题目中，下面我们看一下这个原地置换法，原地置换的大体思路就是将我们指针对应的元素放到属于他的位置（索引对应的地方）。我们可以这样理解，每个人都有自己的位置，我们需要和别人调换回到属于自己的位置，调换之后，如果发现我们的位置上有人了，则返回。

图解👇

代码如下👇

class Solution {public int findRepeatNumber(int[] nums) { if(nums.length == 0) {     return -1; } for (int i = 0; i < nums.length; i++) {  //设索引初始值为 i = 0，遍历整个数组 nums      while (nums[i] != i) {   if (nums[i] == nums[nums[i]]) {    //发现重复元素，直接返回      return nums[i];  }  int tmp = nums[i];      //执行交换操作，目的是为了使索引与值一一对应  nums[i] = nums[tmp];  nums[tmp] = tmp;     } } return -1;    }

以上算法实现的复杂度分析：

• 时间复杂度是： O(n)
• 空间复杂度是 ： O(1)

可以看出，我们利用这种方法， 空间复杂度降到了 O(1) 了。

🌈我的感受：
刚开始看到这道题的时候，想着这还不简单，随随便便一个遍历就敲出来了，做出来之后，看到评论区大佬们的各种高招解法，顿时语塞，我这低端算法根本上不了台面，不过还是高兴了一会，毕竟也是解出来了😂，不愧是剑指offer的题，真没有想象的简单。不过不能放弃，要坚持下去，让我们一起加油，继续努力，共勉～

神唱ktv下载