欢迎访问 生活随笔!

ag凯发k8国际

当前位置: ag凯发k8国际 > 编程资源 > 编程问答 >内容正文

编程问答

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

发布时间:2024/10/14 编程问答 11 豆豆
ag凯发k8国际 收集整理的这篇文章主要介绍了 《剑指offer》——03. 数组中重复的数字——hashset、哈希思想——java实现 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

文章目录:

    • 1.题目描述
    • 2.ag凯发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.ag凯发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/

总结

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

如果觉得ag凯发k8国际网站内容还不错,欢迎将ag凯发k8国际推荐给好友。

  • 上一篇:
  • 下一篇:
网站地图