南京市建筑工程网站,网站信息优化的方式,滑县住房城乡建设厅门户网站,西宁建设网站的公司其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 哈希类算法题注意事项
2.2 方法一#xff1a;哈希法
三、代码
3.1 方法一#xff1a;哈希法
四… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 哈希类算法题注意事项
2.2 方法一哈希法
三、代码
3.1 方法一哈希法
四、复杂度分析
4.1 方法一哈希法 前言
这是力扣的 2215 题难度为简单解题方案有很多种本文讲解我认为最奇妙的一种。 一、题目描述
给你两个下标从 0 开始的整数数组 nums1 和 nums2 请你返回一个长度为 2 的列表 answer 其中
answer[0] 是 nums1 中所有 不 存在于 nums2 中的 不同 整数组成的列表。answer[1] 是 nums2 中所有 不 存在于 nums1 中的 不同 整数组成的列表。
注意列表中的整数可以按 任意 顺序返回。
示例 1 输入nums1 [1,2,3], nums2 [2,4,6]
输出[[1,3],[4,6]]
解释
对于 nums1 nums1[1] 2 出现在 nums2 中下标 0 处然而 nums1[0] 1 和 nums1[2] 3 没有出现在 nums2 中。因此answer[0] [1,3]。
对于 nums2 nums2[0] 2 出现在 nums1 中下标 1 处然而 nums2[1] 4 和 nums2[2] 6 没有出现在 nums2 中。因此answer[1] [4,6]。 示例 2 输入nums1 [1,2,3,3], nums2 [1,1,2,2]
输出[[3],[]]
解释
对于 nums1 nums1[2] 和 nums1[3] 没有出现在 nums2 中。由于 nums1[2] nums1[3] 二者的值只需要在 answer[0] 中出现一次故 answer[0] [3]。
nums2 中的每个整数都在 nums1 中出现因此answer[1] [] 。 提示
1 nums1.length, nums2.length 1000-1000 nums1[i], nums2[i] 1000 二、题解 2.1 哈希类算法题注意事项
解决哈希类的算法题需要注意以下几点
理解哈希表的基本原理哈希表是一种数据结构它使用哈希函数将键映射到数组中的位置。理解哈希表如何工作是解决这类问题的关键。选择合适的哈希函数一个好的哈希函数能够将键均匀地分布到哈希表中以减少冲突。你需要选择或设计一个能够满足题目要求的哈希函数。处理冲突即使有好的哈希函数也可能会有冲突即两个不同的键映射到同一个位置。你需要决定如何处理这些冲突例如使用链表、开放地址法等。考虑哈希表的负载因子负载因子是哈希表中元素的数量与哈希表大小的比值。当负载因子过高时哈希表的性能会下降。因此你可能需要动态调整哈希表的大小以保持合适的负载因子。优化空间和时间效率在解决这类问题时你需要权衡空间和时间效率。一个空间效率高的解决方案可能不那么高效反之亦然。你需要找到一个合适的平衡点。测试和验证在提交解决方案之前一定要进行彻底的测试和验证。确保你的解决方案在各种情况下都能正常工作。阅读和理解题目要求仔细阅读题目确保你完全理解了题目的要求。如果有任何疑问应该向老师或教练询问以确保没有误解。使用适当的数据结构在许多情况下使用哈希表并不是唯一的解决方案。其他数据结构如数组、树或图可能更适合解决特定的问题。选择最适合的数据结构可以提高解决问题的效率。注意算法的复杂度了解算法的时间复杂度和空间复杂度对于选择合适的算法非常重要。对于大规模数据应选择复杂度较低的算法以提高效率。多做练习解决哈希类的算法题需要大量的练习和经验积累。通过参与在线编程挑战、参加算法竞赛等方式可以提高解决这类问题的能力。
2.2 方法一哈希法
思路与算法
为了较快地判断一个数组的某个元素是否在另一个数组中存在我们可以用哈希集合来存储数组的元素并进行判断。具体而言我们用哈希集合 set1 与 set2 存储数组 nums1 与 nums2 中所有不同的元素。
我们用长度为 2 的嵌套列表 res 来保存两数组中不存在于另一数组中的元素。
新建五个空间
reslist1list2set1set2 我们首先遍历哈希集合 num1的每个元素存入 list1 中然后遍历哈希集合 num2 的每个元素存入 list2 中。
接着遍历 num1 和 num2 。
如果 set2 不存在 num1 的元素同时 list2 不存在这个元素则加入到 list2 中。如果 set1 不存在 num2 的元素同时 list1 不存在这个元素则加入到 list1 中。
最后把 list1 和 list2 加入到 res 中。 三、代码
3.1 方法一哈希法
Java版本
class Solution {public ListListInteger findDifference(int[] nums1, int[] nums2) {ListListInteger res new ArrayList();HashSetInteger set1 new HashSet();HashSetInteger set2 new HashSet();ArrayListInteger list1 new ArrayList();ArrayListInteger list2 new ArrayList();for (int i : nums1) {set1.add(i);}for (int i : nums2) {set2.add(i);}for (int i : nums1) {if (!set2.contains(i)!list2.contains(i)) list2.add(i);}for (int i : nums2) {if (!set1.contains(i)!list1.contains(i)) list1.add(i);}res.add(list2);res.add(list1);return res;}
}
C版本
class Solution {
public:std::vectorstd::vectorint findDifference(std::vectorint nums1, std::vectorint nums2) {std::vectorstd::vectorint res;std::unordered_setint set1(nums1.begin(), nums1.end());std::unordered_setint set2(nums2.begin(), nums2.end());std::vectorint list1, list2;for (int i : nums1) {if (set2.find(i) set2.end() std::find(list2.begin(), list2.end(), i) list2.end()) {list2.push_back(i);}}for (int i : nums2) {if (set1.find(i) set1.end() std::find(list1.begin(), list1.end(), i) list1.end()) {list1.push_back(i);}}res.push_back(list2);res.push_back(list1);return res;}
};Python版本
class Solution:def findDifference(self, nums1, nums2):res []set1 set(nums1)set2 set(nums2)list1 [i for i in nums1 if i not in set2]list2 [i for i in nums2 if i not in set1]res.append(list2)res.append(list1)return resGo版本
import sortfunc findDifference(nums1 []int, nums2 []int) [][]int {res : make([][]int, 2)set1 : make(map[int]bool)set2 : make(map[int]bool)for _, num : range nums1 {set1[num] true}for _, num : range nums2 {set2[num] true}for _, num : range nums1 {if !set2[num] {res[1] append(res[1], num)set2[num] true}}sort.Ints(res[1])for _, num : range nums2 {if !set1[num] {res[0] append(res[0], num)set1[num] true}}sort.Ints(res[0])return res
}四、复杂度分析
4.1 方法一哈希法
时间复杂度O(N)。空间复杂度O(N)。
