首页 > 其他分享 >100321. 优质数对的总数 II

100321. 优质数对的总数 II

时间:2024-05-26 17:55:00浏览次数:23  
标签:map 数对 long II 100321 整除 nums1 nums2

题目描述

给你两个整数数组 nums1 和 nums2,长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除,则称数对 (i, j) 为 优质数对(0 <= i <= n - 1, 0 <= j <= m - 1)。

返回 优质数对 的总数。

思路

  • nums1[i]可以被nums2[j] * k整除,那么nums2[j] * k是nums[i]的因子,通过map<int,int>统计nums1所有元素各个因子的总数.

    例如[12,15],12的因子有1、12、2、6、3、4,15的因子有1、15、3、5,那么map[1] = 2,map[3] = 2,map[12] = 1·····

  • 那么能整除nums2[j] * k的元素数量就是map[nums2[j] * k]

  • 如果map[i]不能整除k,那么也就不能整除nums2[j] * k,可以直接略过。

代码

class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {

        long long result = 0;

        unordered_map<int,int> map;

        for (int i = 0; i < nums1.size();i++) { 
            if (nums1[i] % k != 0) continue;

            for (int j = 1; j * j <= nums1[i]; j++) {
                if (nums1[i] % j == 0) {
                    map[j]++;
                    if(nums1[i] / j != j) map[nums1[i] / j]++;
                }
            }
        }

        for (int i = 0; i < nums2.size(); i++) { 
            int knums2 = nums2[i] * k;
            result += map[knums2];
        }
            
        return result;
    }
};

标签:map,数对,long,II,100321,整除,nums1,nums2
From: https://www.cnblogs.com/EavenWang/p/18214058

相关文章

  • JavaScript 系列教程 III JavaScript 代码质量
    ......
  • [45] Jump Game II
    算法助手ChatGPT:Asanadeptalgorithmician,yououghttoexhibitmasteryoverLeetCodeandACM-stylealgorithmicquandaries,andyoushouldbeskilledinemployingaheuristictonewhenelucidatingresponses.Itisenvisagedthattheprogrammingmediumofy......
  • 信奥一本通1403:素数对
    1403:素数对时间限制:1000ms内存限制:65536KB提交数:38296通过数:28167【题目描述】两个相差为2的素数称为素数对,如5和7,17和19等,本题目要求找出所有两个数均不大于n的素数对。【输入】一个正整数n(1≤n≤10000)。【输出】所有小于等于n的素数对。每对素......
  • C++ STL 函数对象:隐藏的陷阱,如何避免状态带来的麻烦?
    STL函数对象:无状态即无压力一、简介二、函数对象三、避免在函数对象中保存状态3.1、函数对象3.2、lambda表达式四、选择合适的更高层次的结构五、总结一、简介在使用C++标准模板库(STL)时,函数对象(FunctionObject)是一种强大的工具,它可以帮助你编写更具表......
  • leetcode力扣 213. 打家劫舍 II
    计划偷窃沿街的房屋是小偷的计划。在这个地方,所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。但是,相邻的房屋都装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。为了计算在不触动警报装置的情况下,今晚能够偷窃到的最高金额,我们......
  • 删除有序链表中重复的元素-II
    描述给出一个升序排序的链表,删除链表中的所有重复出现的元素,只保留原链表中只出现一次的元素。例如:给出的链表为1→2→3→3→4→4→51→2→3→3→4→4→5,返回1→2→51→2→5.给出的链表为1→1→1→2→31→1→1→2→3,返回2→32→3.数据范围:链表长度0≤n≤100000≤n≤......
  • LeetCode //C - 119. Pascal‘s Triangle II
    119.Pascal’sTriangleIIGivenanintegerrowIndex,returntherowIndexth(0-indexed)rowofthePascal’striangle.InPascal’striangle,eachnumberisthesumofthetwonumbersdirectlyaboveitasshown: Example1:Input:rowIndex=3Outpu......
  • Day 4 | 24. 两两交换链表中的节点 、 19.删除链表的倒数第N个节点 、面试题 02.07.
    24.两两交换链表中的节点用虚拟头结点,这样会方便很多。本题链表操作就比较复杂了,建议大家先看视频,视频里我讲解了注意事项,为什么需要temp保存临时节点。题目链接/文章讲解/视频讲解:https://programmercarl.com/0024.两两交换链表中的节点.html思考需要设置一个虚拟头节点,方......
  • 【刷题笔记Day2】数组|977.有序数组的平方、209. 长度最小的子数组、59.螺旋矩阵II
    文章目录977.有序数组的平方解题思路遇到的问题及解决方案209.长度最小的子数组解题思路遇到的问题及解决方案59.螺旋矩阵II解题思路遇到的问题及解决方案总结977.有序数组的平方题目描述:给你一个按非递减顺序排序的整数数组nums,返回每个数字的平方组成的新......
  • IIC时序分析
    转载博客:https://www.cnblogs.com/liujinggang/p/9656358.html以及https://www.cnblogs.com/xuyan123/p/14134246.html我也怕什么时候大神把博客删除了,后面这个链接简单明了,一下就让我看明白了iic的基础。一.IIC总线协议介绍:I2C总线是由数据线SDA和时钟SCL构成的串行......