首页 > 其他分享 >两个有序数组的第K小乘积

两个有序数组的第K小乘积

时间:2023-05-29 23:56:30浏览次数:36  
标签:p2 乘积 int long nums1 vector 有序 数组 cur

给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k 
请你返回第 k (从 1 开始编号)小的 nums1[i] * nums2[j] 的乘积

1. 二分查找

class Solution {
public:
    typedef long long ll;
    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        //时间复杂度O(m*n*10glog10)
        vector<int> p1,p2,n1,n2;
        //将正数负数分开
        for(int x:nums1) (x<0)?n1.push_back(x):p1.push_back(x); //n存储负数,p存储正数
        for(int x:nums2) (x<0)?n2.push_back(x):p2.push_back(x);
        ll l=-1e10,r=1e10; //初始化左右边界
        while(l<r){
            ll m=(l+r)>>1;
            ll cur=0;//计数
            //找满足乘积小于等于mid的个数
            for(int i=0,j=p2.size()-1;i<p1.size();i++){   //正数和正数
                while(j>=0&&1LL*p1[i]*p2[j]>m) j--; //指针前移,j及之前的坐标都满足要求,总个数为j+1
                cur+=j+1;
            }
            for(int i=0,j=0;i<p1.size();i++){  //正数和负数
                while(j<n2.size()&&1LL*p1[i]*n2[j]<=m) j++; //指针后移,j之前的坐标都满足要求,总个数为j
                cur+=j;
            }
            for(int i=0,j=n2.size()-1;i<n1.size();i++){//负数和负数
                while(j>=0&&1LL*n1[i]*n2[j]<=m) j--; //指针前移,j之后为满足条件的个数,前面有j+1个数,减去
                cur+=n2.size()-(j+1); //加上后面的个数
            }
            for(int i=0,j=0;i<n1.size();i++){//负数和正数
                while(j<p2.size()&&1LL*n1[i]*p2[j]>m) j++; //指针后移,j及之后的为满足条件的个数,前面有j个数,减去
                cur+=p2.size()-j;
            }

            if(cur<k) l=m+1;//不满足条件
            else r=m; 
        }
        return r;
    }
};

2. 二分 + 二分

优化方法一中对另一个数组的暴力查找
只优化了正数和正数的查找,貌似性能更差,不再继续优化

class Solution {
public:
    typedef long long ll;
    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        //时间复杂度O(m*n*10glog10)
        vector<int> p1,p2,n1,n2;
        //将正数负数分开
        for(int x:nums1) (x<0)?n1.push_back(x):p1.push_back(x); //n存储负数,p存储正数
        for(int x:nums2) (x<0)?n2.push_back(x):p2.push_back(x);
        ll l=-1e10,r=1e10; //初始化左右边界
        while(l<r){
            ll m=(l+r)>>1;
            ll cur=0;//计数
            //找满足乘积小于等于mid的个数
            for(int i=0,j=p2.size()-1;i<p1.size();i++){   //正数和正数
                if(p1[i]==0) j = m>=0?p2.size():0;
                else {
                    double val = (double)m/p1[i];
                    auto leftbound = upper_bound(p2.begin(), p2.end(), val);
                    j = leftbound - p2.begin();
                }
                cur+=j;
            }
            for(int i=0,j=0;i<p1.size();i++){  //正数和负数
                while(j<n2.size()&&1LL*p1[i]*n2[j]<=m) j++; //指针后移,j之前的坐标都满足要求,总个数为j
                cur+=j;
            }
            for(int i=0,j=n2.size()-1;i<n1.size();i++){//负数和负数
                while(j>=0&&1LL*n1[i]*n2[j]<=m) j--; //指针前移,j之后为满足条件的个数,前面有j+1个数,减去
                cur+=n2.size()-(j+1); //加上后面的个数
            }
            for(int i=0,j=0;i<n1.size();i++){//负数和正数
                while(j<p2.size()&&1LL*n1[i]*p2[j]>m) j++; //指针后移,j及之后的为满足条件的个数,前面有j个数,减去
                cur+=p2.size()-j;
            }

            if(cur<k) l=m+1;//不满足条件
            else r=m; 
        }
        return r;
    }
};

标签:p2,乘积,int,long,nums1,vector,有序,数组,cur
From: https://www.cnblogs.com/929code/p/17442047.html

相关文章

  • 代码随想录算法训练营第六天|哈希表理论基础、242.有效的字母异位词两个数组的交集、2
    242.有效的字母异位词力扣题目链接(opensnewwindow)给定两个字符串s和t,编写一个函数来判断t是否是s的字母异位词。示例 1:输入:s="anagram",t="nagaram"输出:true示例2:输入:s="rat",t="car"输出:false说明: 你可以假设字符串只包含小写字母。思路:......
  • hdu 3874(树状数组+离线算法)
    解题思路:这道题和之前的题一样,查找[l,r]区间内不重复数字的和。可以利用离线算法,实际上离线算法为了解决在查找时出现的矛盾,因为每次询问的区间大小不同,如果单独处理的话可能会对之后的查询有影响,所以离线算法帮助我们把要查询的区间先按照右端点进行排序,因为在处理更靠右的区间时,......
  • 2023-05-29:给你一个由 n 个正整数组成的数组 nums 你可以对数组的任意元素执行任意次
    七、设计算法,仅使用三次实数乘法即可完成复数a+bi和c+di相乘。算法需接收a、b、c和d为输入,分别生成实部ac-bd和虚部ad+bc。文心一言:可以使用如下算法来计算复数a+bi和c+di的积,且只需进行三次实数乘法:1.将a和b相乘,得到ab;2.将c和d相乘,得到cd;3.将ab+cd赋......
  • 斐波那契数列:2.数组
    斐波那契数列:2.数组#include<stdio.h>intfib(intm){inti;inta[100]={0,1,1};for(i=2;i<=m;i++){a[i]=a[i-1]+a[i-2];}returna[m];}intmain(){intn;scanf("%d",&n);printf("%d",fib(n));return0......
  • 33. 搜索旋转排序数组
    分析:A对于题目中定义的旋转数组,从中间一分为二。一定是被分为一个有序数组,一个旋转数组(循环数组)。B若对旋转数组再次从中间分割,会重复A的操作。对有序数组二分可看做普通二分查找一致操作。定理一:只有在顺序区间内才可以通过区间两端的数值判断target是否在其中。定理二:判......
  • js-01_数组
    数组的常用方法数组常用方法之pushpush是用来在数组的末尾追加一个元素vararr=[1,2,3]//使用push方法追加一个元素在末尾arr.push(4)console.log(arr)//[1,2,3,4]数组常用方法之poppop是用来删除数组末尾的一个元素vararr=[1,2,3]//使......
  • hdu 4417(树状数组+离线算法)
    解题思路:这道题要求某区间内比h小的个数,其实这里可以类似于树状数组求逆序数那样。关键是如何转换成树状数组的模型,这才是本题的难点。我们首先分析,如果知道h在该区间的哪个位置,那么剩下的就很好做了。我们还可以发现,如果找到了当前的比h小的所有点(大于的点我们先忽略掉),那么我们就......
  • poj 1195(二维树状数组)
    解题思路:这是一道很裸的二维树状数组AC:#include<stdio.h>#include<string.h>#defineN1100intc[N][N],n,arr[N][N];intlowbit(intx){returnx&(-x);}voidupdate(intx,inty,intnum){inti,j;for(i=x;i<=n;i+=lowbit(i))for(j=y;......
  • hdu 5157(manacher+前缀和+树状数组)
    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5157解题思路:我们可以先用mancher算法对字符串进行处理,把以每个点为中心的回文串半径求出来,然后进行处理。加入对以p为中心的点,从p-r[i]+1~p都是回文串的开头,那么对于每个回文串(开头是j)只要记录结尾从1~j-1的回文串个数,我们可......
  • 【蓝桥杯 2019 省 A】修改数组【并查集】
    链接https://www.luogu.com.cn/problem/P8686题意给你\(n\)个数a[1...n],从\(a_2\)开始,如果和之前的某个数具有相等的值,就一直让\(a_i=a_i+1\),直到前面的任何一个数都和它不相等\(1\leqn\leq10^5\),\(1\leqa_i\leq10^6\)问最后的序列是什么思路暴力做法......