算法笔记-两数组交集

| 2024-04-16 |

随谈：前言越来越想是随谈了，所以之后就改叫随谈算了，因为项目要赶着交 Demo，所以我这礼拜就一直忙着先弄项目那边了。我现在认识到，自己有时候写东西还挺烦的，思路没理清就开始写，导致团队伙伴带来了很多麻烦，学算法，一是要锻炼自己的逻辑能力，二就是要让自己耐心。很多事情自己知道是有问题的，但忍不住问，这种其实是无效发言。会让别人觉得你自己很不细心和靠谱。所以向别人提问之前，先三思一下。做完之后，以防万一再向别人确认。

# 题目：

给定两个数组 nums1 和 nums2 ，返回 它们的

交集

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

示例 1：
1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
1
2
3
输入：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

这题就是考哈希表了。所以直接给出答案

这里贴一下我以前的算法解答

public class Intersect
{
    #region 使用哈希表

    public static int[] GetIntersect2(int[] nums1, int[] nums2)
    {
        if (nums1.Length > nums2.Length) {
            return GetIntersect2(nums2, nums1);
        }
        Dictionary<int, int> map = new Dictionary<int, int>();
        foreach (int num in nums1) {
            int count = map.GetValueOrDefault(num, 0) + 1;
            map[num] = count;
        }
        
        int[] intersection = new int[nums1.Length];
        int index = 0;
        foreach (int num in nums2) {
            int count = map.GetValueOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map[num] = count;
                } else {
                    map.Remove(num);
                }
            }
        }
        return intersection.Take(index).ToArray();
    }

    #endregion

    #region 使用Linq的方案

    public static void GetIntersect1(int[] array1, int[] array2)
    {
        var intersection = array1
            .GroupBy(x => x) // 对数组1中的元素进行分组
            .Join(array2
                    .GroupBy(y => y), // 对数组2中的元素进行分组
                x => x.Key, // 使用数组1中的元素作为键
                y => y.Key, // 使用数组2中的元素作为键
                (x, y) => new { Element = x.Key, Count = Math.Min(x.Count(), y.Count()) } // 计算重复次数的最小值
            )
            .SelectMany(x => Enumerable.Repeat(x.Element, x.Count)) // 重复每个元素Count次
            .ToArray(); // 将结果转换为数组
    }

    #endregion
}

新的解答：

public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
        //用字典存储第一个数组的所有数字
        Dictionary<int,int> numDic = new();
        List<int> resultList = new();
        
        for(int i= 0;i< nums1.Length;i++){
            numDic.TryAdd(nums1[i],0);
        }
        for(int i= 0;i< nums2.Length;i++)
        {    
            if(numDic.TryGetValue(nums2[i],out int show)){
                numDic[nums2[i]]++;
                if(numDic[nums2[i]] == 1){
                    resultList.Add(nums2[i]);
                }  
            }
        }
        int[] result = new int[resultList.Count];
        for(int i=0;i<result.Length;i++){
            result[i] = resultList[i];
        }
        return result;
    }
}

这题为简单题。可以自己完全写出来但不管写什么都先把思绪理清楚

tags: #算法