0 课程地址
https://coding.imooc.com/lesson/207.html#mid=13711
1 重点关注
1.1 结论
- 3.1和3.2对比
3.2空间复杂度优于3.1
- 3.3和3.4对比
HashMap无序速度优于TreeMap(见3-2，HashSet实现)
- 3.5和3.3，3.4对比
数组使用空间复杂度优于集合或者Set
2 课程内容
3 Coding
3.1 LeetCode 349问题 Set应用 常规方法
- 需求
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-arrays
- 设计思路：
组装成两个set，由于每个set键值唯一,for循环，可以判断出交集 复杂度2*O(h)
- coding:
package com.company;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;
/**
* 设计思路：组装成两个set，由于每个set键值唯一,for循环，可以判断出交集 复杂度2*O(h)
* @author weidoudou
* @date 2023/1/2 15:54
**/
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new TreeSet();
for(int num1:nums1){
set1.add(num1);
}
Set<Integer> set2 = new TreeSet<>();
for(int num2:nums2){
set2.add(num2);
}
/* int[] ints = {};
Iterator iterator = set2.iterator();
while (iterator.hasNext()){
if(set2.contains(iterator.next())){
ints.
}
}*/
int[] ints = set2.stream().map(
e->{
if(set1.contains(e)){
return e;
}
return null;
}
).filter(Objects::nonNull).mapToInt(Integer::valueOf).toArray();
return ints;
}
}
- 解题结果：
3.2 LeetCode 349问题 Set应用 时间复杂度优化
- 需求
见3.1
- 设计思路：
只组装一个set,有一次包含，set去一个元素，同样判断出交集 复杂度O(h)
- coding:
package com.company;
import java.util.*;
/**
* 设计思路：只组装一个set,有一次包含，set去一个元素，同样判断出交集 复杂度O(h)
* @author weidoudou
* @date 2023/1/2 15:54
**/
class Solution2 {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new TreeSet();
for(int num1:nums1){
set1.add(num1);
}
List<Integer> list = new ArrayList<>();
for(int num :nums2){
if(set1.contains(num)){
list.add(num);
set1.remove(num);
}
}
int[] ints = list.stream().mapToInt(Integer::valueOf).toArray();
return ints;
}
}
- 解题结果：
3.3 LeetCode 350问题 Map应用 常规做法
- 需求
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-arrays-ii
- 设计思路：
使用映射来解决问题，其中value记录次数
- coding:
package com.company;
import java.util.*;
/**
* 设计思路：使用映射来解决问题，其中value记录次数
* @author weidoudou
* @date 2023/1/2 15:54
**/
class Solution3 {
public int[] intersection(int[] nums1, int[] nums2) {
Map<Integer,Integer> treeMap = new TreeMap();
for(int num :nums1){
if(treeMap.containsKey(num)){
treeMap.put(num,treeMap.get(num)+1);
}else{
treeMap.put(num,1);
}
}
List<Integer> list = new ArrayList<>();
for(int i = 0;i<nums2.length;i++){
if(treeMap.containsKey(nums2[i])){
list.add(nums2[i]);
Integer temp = treeMap.get(nums2[i]);
if(temp>1){
treeMap.put(nums2[i], temp-1);
}else{
treeMap.remove(nums2[i]);
}
}
}
int[] ints = list.stream().mapToInt(Integer::valueOf).toArray();
return ints;
}
}
- 解题结果：
3.4 LeetCode 350问题 Map应用 HashMap
- 需求
如3.3
- 设计思路：
HashMap底层用Hash表实现，优于TreeMap
- coding:
package com.company;
import java.util.*;
/**
* 设计思路：使用映射来解决问题，其中value记录次数
* @author weidoudou
* @date 2023/1/2 15:54
**/
class Solution4 {
public int[] intersection(int[] nums1, int[] nums2) {
Map<Integer,Integer> hashMap = new HashMap<>();
for(int num :nums1){
if(!hashMap.containsKey(num)){
hashMap.put(num,1);
}else{
hashMap.put(num,hashMap.get(num)+1);
}
}
List<Integer> list = new ArrayList<>();
for(int i = 0;i<nums2.length;i++){
if(hashMap.containsKey(nums2[i])){
list.add(nums2[i]);
Integer temp = hashMap.get(nums2[i]);
if(temp>1){
hashMap.put(nums2[i], temp-1);
}else{
hashMap.remove(nums2[i]);
}
}
}
int[] ints = list.stream().mapToInt(Integer::valueOf).toArray();
return ints;
}
}
- 解题结果：
3.5 LeetCode 350问题 数组实现
- 需求
如3.3
- coding:
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
int[] arr = new int[1002];
// 先遍历nums1记录各个数的个数
for (int j : nums1) {
arr[j]++;
}
int size = 0;
List<Integer> list = new LinkedList<>();
// 遍历nums2，从arr中查找和nums1有无相同数字，若存在则用list暂存一下，并且将该数字的计数减一，用size记录最后的数组大小
for (int j : nums2) {
if (arr[j] != 0) {
size++;
arr[j]--;
list.add(j);
}
}
int[] ans = new int[size];
int in = 0;
for (Integer n : list) {
ans[in++] = n;
}
return ans;
}
}
- 解题结果：
标签：int,list,Leetcode,num,玩转,new,数据结构,nums1,nums2 From： https://www.cnblogs.com/1446358788-qq/p/17020293.html