哈希集合用法及算法例题

[qingmei2]

哈希集合用法及算法例题

本文为博主算法学习过程中的学习笔记，主要内容来源于其他平台或书籍，出处请参考下方 参考&感谢 一节。

用法

哈希集 是集合的实现之一，它是一种存储 不重复值 的数据结构。

因此，通常，使用哈希集来检查该值是否已经出现过。

让我们来看一个例子：

给定一个整数数组，查找数组是否包含任何重复项。

这是一个典型的问题，可以通过哈希集来解决。

你可以简单地迭代每个值并将值插入集合中。 如果值已经在哈希集中，则存在重复。

例题

1、存在重复元素

题目描述

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例:

输入: [1,2,3,1]
输出: true

解题思路及实现

HashSet的入门题，最基本模版的实现。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            } else {
                set.add(nums[i]);
            }
        }
        return false;
    }
}

2、只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

示例:

输入: [2,2,1]
输出: 1

解题思路及实现

这道题解决方案有很多种，HashSet是其中的一种解法，也比较基础。

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
            } else {
                set.remove(nums[i]);
            }
        }
        return set.iterator().next();
    }
}

3、两个数组的交集

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

• 输出结果中的每个元素一定是唯一的。
• 我们可以不考虑输出结果的顺序。

解题思路及实现

有点繁琐，HashSet的暴力破解法：

class Solution {
  public int[] intersection(int[] nums1, int[] nums2) {
      // 暴力破解之
      int len1 = nums1.length;
      int len2 = nums2.length;
      if (len1 == 0 || len2 == 0) return new int[]{};

      HashSet<Integer> set1 = new HashSet<>();
      for (int i = 0; i < len1; i++)
          set1.add(nums1[i]);
      HashSet<Integer> set2 = new HashSet<>();
      for (int i = 0; i < len2; i++)
          set2.add(nums2[i]);

      int[] result = new int[set1.size()];
      int index = 0;
      for (int value : set1) {
          if (set2.contains(value)) {
              result[index] = value;
              index++;
          }
      }
      return Arrays.copyOf(result,index);
  }
}

4、快乐数

题目描述

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例:

输入: 19
输出: true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

解题思路及实现

这道题是非常有意思的一道题，可以思考不难得出，这种一个正整数的循环计算，每位上数字的平方和，计算结果最多也就3、4位数——也就是说，最终经过有限的步骤，最终都会进入循环。

因此我们每次计算都将结果存入HashSet，出现1时自然就是快乐数；而当出现循环时若结果还没有出现1，意味着接下来再也不会出现1，因此这个数字也就不是快乐数了:

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        set.add(n);

        while (true) {
            n = change(n);
            if (n == 1)
                return true;
            if (set.contains(n)) {
                return false;
            } else {
                set.add(n);
            }
        }
    }

    private int change(int n) {
        int sum = 0;
        while (n > 0) {
            int bit = n % 10;
            sum += bit * bit;
            n = n / 10;
        }
        return sum;
    }
}

之所以说这道题有意思的地方在于，另外一种视角来看，我们可以将每次计算的结果串联起来，这样问题就转换为了 弗洛伊德的乌龟与兔子 问题，通过 快慢指针 进行解决。

参考 & 感谢

文章绝大部分内容节选自LeetCode，概述：

• https://leetcode-cn.com/explore/learn/card/hash-table/204/practical-application-hash-set/803/

例题：

• https://leetcode-cn.com/problems/contains-duplicate/
• https://leetcode-cn.com/problems/single-number/
• https://leetcode-cn.com/problems/intersection-of-two-arrays/
• https://leetcode-cn.com/problems/happy-number/

关于我

Hello，我是 却把清梅嗅 ，如果您觉得文章对您有价值，欢迎 ❤️，也欢迎关注我的 博客 或者 GitHub。

如果您觉得文章还差了那么点东西，也请通过关注督促我写出更好的文章——万一哪天我进步了呢？

• 我的Android学习体系
• 关于文章纠错
• 关于知识付费
• 关于《反思》系列