2956、找到两个数组中的公共元素

leetcode 数组哈希表

Created At : 2024-07-16 23:19

Count:455 Views 👀 :

Comment:

题目
分析
1. 哈希表
2. 优化一下代码

题目

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，它们分别含有 n 和 m 个元素。请你计算以下两个数值：

answer1：使得 nums1[i] 在 nums2 中出现的下标 i 的数量。
answer2：使得 nums2[i] 在 nums1 中出现的下标 i 的数量。
返回 [answer1, answer2]。

示例 1：

输入：nums1 = [2,3,2], nums2 = [1,2]

输出：[2,1]

解释：

示例 2：

输入：nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]

输出：[3,4]

解释：

nums1 中下标在 1，2，3 的元素在 nums2 中也存在。所以 answer1 为 3。

nums2 中下标在 0，1，3，4 的元素在 nums1 中也存在。所以 answer2 为 4。

示例 3：

输入：nums1 = [3,4,2,3], nums2 = [1,5]

输出：[0,0]

解释：

nums1 和 nums2 中没有相同的数字，所以答案是 [0,0]。

提示：

n == nums1.length
m == nums2.length
1 <= n, m <= 100
1 <= nums1[i], nums2[i] <= 100

分析

不同数组中交集的元素数目

哈希表

class Solution {
    public int[] findIntersectionValues(int[] nums1, int[] nums2) {
        int[] count1 = new int[101];
        int[] count2 = new int[101];
        for(int i  = 0;i < nums1.length;i++) {
            count1[nums1[i]]++;
        }
        int[] answer = new int[2];
        for(int i  = 0;i < nums2.length;i++) {
            if (count1[nums2[i]] > 0) {
                answer[0] += count1[nums2[i]];
                count1[nums2[i]] = 0 - count1[nums2[i]];
                
            }
            count2[nums2[i]]++;
        }
        for(int i  = 0;i < nums2.length;i++) {
            if (count1[nums2[i]] < 0 && count2[nums2[i]] > 0) {
                answer[1] += count2[nums2[i]];
                count2[nums2[i]] = 0 - count2[nums2[i]];
            }
        }

        return answer;
    }
}

优化一下代码

class Solution {
    public int[] findIntersectionValues(int[] nums1, int[] nums2) {
        // 统计nums1里面的频率
        int[] counter = new int[101];
        for(int num : nums1){
            counter[num]++;
        }
        int[] ans = new int[2];
        for(int num : nums2){
            // 如果counter[num] = 0 表面没有交集
            ans[1] += counter[num] != 0 ? 1 : 0;
            // 如果num出现多次，每次都+1
            if(counter[num] > 0){
                ans[0] += counter[num];
                counter[num] = -1;
            }
        }

        return ans;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com