《剑指offer》——03. 数组中重复的数字——hashset、哈希思想——java实现 -凯发k8官方网

文章目录：

• • 1.题目描述
  • 2.凯发k8官方网的解决方案
  • • （1）hashset方法解决
    • （2）哈希思想(巧解)
  • 3.参考

---

1.题目描述

找出数组中重复的数字。
        在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
        [2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
        2 <= n <= 100000

2.凯发k8官方网的解决方案

（1）hashset方法解决

• 使用 hashset 来进行处理，因为 hashset 本身不允许出现重复元素，所以当添加元素失败或已经包含该数字时，则表示出现了重复元素，将其返回即可。
• 时间复杂度：o(n)，空间复杂度：o(n)
• 时间复杂度为o(n)，是因为有for循环
• 空间复杂度为o(n)，是因为new hashset()申请了空间

class solution {public int findrepeatnumber(int[] nums) {set<integer> demo= new hashset<>();for(int a: nums) {if(!demo.add(a)) {return a;}}return -1;} }

（2）哈希思想(巧解)

• 所有数字都在 0 ～ n-1 的范围内，将每个位置的数交换映射到其对应的数组下标下面，当出现新的元素与其对应的下标中的数字相等时，即为重复数字
• 哈希的思想，数组本身做哈希表，达到了节省空间的目的
• while 循环，保证交换过来的新元素位置也要正确，即令：a[i]=i 。
• 时间复杂度：o(n)，空间复杂度：o(1)
• 看图了解其过程：
  
  

class solution {public int findrepeatnumber(int[] nums) {int len = nums.length;for (int i = 0; i < len; i) {while (nums[i] != i) {//保证交换过来的新元素位置也要正确，即令：a[i]=i if (nums[i] == nums[nums[i]]) {//将每个位置的数交换映射到其对应的数组下标下面，当出现新的元素与其对应的下标中的数字相等时，即为重复数字return nums[i]; }int temp = nums[i]; //交换，使对应下标的数组值与其下标值相等，即令 a[i]=inums[i] = nums[temp];nums[temp] = temp;}}return -1;} }

3.参考

链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/hua-jie-suan-fa-mian-shi-ti-3-shu-zu-zhong-zhong-f/

总结

以上是凯发k8官方网为你收集整理的《剑指offer》——03. 数组中重复的数字——hashset、哈希思想——java实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发k8官方网网站内容还不错，欢迎将凯发k8官方网推荐给好友。