首页 / 算法 / leetcode 查找算法
leetcode 查找算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode 查找算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3825字，纯文字阅读大概需要6分钟。
内容图文
查找表：考虑的基本数据结构
第一类： 查找有无--set
元素'a'是否存在，通常用set：集合
set只存储键，而不需要对应其相应的值。
set中的键不允许重复
第二类： 查找对应关系(键值对应)--map
元素'a'出现了几次：dict-->字典
dict中的键不允许重复
第三类： 改变映射关系--map
通过将原有序列的关系映射统一表示为其他
题目描述：
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
说明：
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
解题思路：
用两个HashSet分别统统计两个数组，然后找出两个set中公共元素
代码：
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set1 = new HashSet<>();
for (Integer num : nums1) {
set1.add(num);
}
HashSet<Integer> set2 = new HashSet<>();
for (Integer num : nums2) {
set2.add(num);
}
return set1.size() < set2.size() ? help(set1, set2) : help(set2, set1);
}
private int[] help(HashSet<Integer> set1, HashSet<Integer> set2) {
int[] output = new int[set1.size()];
int index = 0;
for (Integer s : set1){
if (set2.contains(s))
output[index++] = s;
}
return Arrays.copyOf(output, index);
}
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)，因为开辟了新的数组output 长度与输入的数据大小有关。
题目描述：
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
?
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶：
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果?nums1?的大小比?nums2?小很多，哪种方法更优？
如果?nums2?的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
解题思路：
跟上一道题目不同的是，这个可以有重复元素，所以可以考虑采用hashmap
方法一：采用上述题目的套路，效率低
方法二：使用hash表存储，效率高
方法一：
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> map1 = new HashMap<>();
HashMap<Integer, Integer> map2 = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
map1.put(nums1[i], map1.getOrDefault(nums1[i], 0) + 1);
}
for (int i = 0; i < nums2.length; i++) {
map2.put(nums2[i], map2.getOrDefault(nums2[i], 0) + 1);
}
int n = nums1.length < nums2.length ? nums1.length : nums2.length;
int[] output = new int[n];
int index = 0;
for (Map.Entry<Integer, Integer> map : map1.entrySet()) {
if (map2.containsKey(map.getKey())) {
int temp = map2.get(map.getKey()) < map.getValue() ? map2.get(map.getKey()) : map.getValue();
for (int i = 0; i < temp; i++) {
output[index++] = map.getKey();
}
}
}
return Arrays.copyOf(output, index);
}
复杂度分析：
- 时间复杂度：O(n*n)
- 空间复杂度：O(min(m,n))
方法二：采用hash表
思路：
由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。
public int[] intersect2(int[] nums1, int[] nums2) {
// 保证 nums1的长度始终最小
if (nums1.length > nums2.length)
return intersect2(nums2, nums1);
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums2.length; i++) {
map.put(nums2[i], map.getOrDefault(nums2[i], 0) + 1);
}
int n = nums1.length;
int[] output = new int[n];
int index = 0;
for (Integer num : nums1) {
int count = map.getOrDefault(num, 0);
if (count > 0) {
output[index++] = num;
count--;
if (count > 0) {
map.put(num, count);
} else {
map.remove(num);
}
}
}
return Arrays.copyOf(output, index);
}
复杂度分析：
- 时间复杂度：O(n + m)
- 空间复杂度：O(min(m,n))
两者性能对比：
未完待续
内容总结
以上是互联网集市为您收集整理的leetcode 查找算法全部内容，希望文章能够帮你解决leetcode 查找算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。