米鼠商城

多块好省,买软件就上米鼠网

最新项目

人才服务

靠谱的IT人才垂直招聘平台

按位与为零的三元组--哈希表优化循环

  • lxd01
  • 7
  • 2020-03-21 19:35

0x01.问题

给定一个整数数组 A,找出索引为 (i, j, k) 的三元组,使得: 0 <= i < A.length 0 <= j < A.length 0 <= k < A.length A[i] & A[j] & A[k] == 0,其中 & 表示按位与(AND)操作符。 输入示例:[2,1,3] 输出示例:12 解释:我们可以选出如下 i, j, k 三元组: (i=0, j=0, k=1) : 2 & 2 & 1 (i=0, j=1, k=0) : 2 & 1 & 2 (i=0, j=1, k=1) : 2 & 1 & 1 (i=0, j=1, k=2) : 2 & 1 & 3 (i=0, j=2, k=1) : 2 & 3 & 1 (i=1, j=0, k=0) : 1 & 2 & 2 (i=1, j=0, k=1) : 1 & 2 & 1 (i=1, j=0, k=2) : 1 & 2 & 3 (i=1, j=1, k=0) : 1 & 1 & 2 (i=1, j=2, k=0) : 1 & 3 & 2 (i=2, j=0, k=1) : 3 & 2 & 1 (i=2, j=1, k=0) : 3 & 1 & 2 提示:1 <= A.length <= 1000 0 <= A[i] < 2^16

C++函数形式为   int countTriplets(vector<int>& A)

0x02.分析

三元组进行按位与,正常思路肯定是要三层循环,但是细看一下A的范围,到达了1000,如果三层循环,肯定超时,所以我们必须优化一下。

用三层循环的目的就是保证每三个数都能进行一次按位与操作,我们可不可以先计算出两个与操作的值,再对每个数,与这两个的值进行按位与操作呢?

肯定是可以的,但需要记录下每两个按位与产生的值出现的频率,因为这是和次数挂钩的。

我们可以用一个哈希表记录每两个按位与操作产生的值的数量,再用一个哈希表记录每个元素出现的数量,这样就可以避免重复操作。

这样,三层循环就变成了两层循环。

0x03.解决代码

class Solution {
public:
    int countTriplets(vector<int>& A) {
        unordered_map<int,int> map1;
        unordered_map<int,int> map2;
        for(int n:A) map1[n]++;
        for(int i=0;i<A.size();i++){
            for(int j=0;j<A.size();j++){
                map2[A[i] & A[j]]++;
            }
        }
        int ans=0;
        for(auto p1:map1){
            for(auto p2:map2){
                if((p1.first & p2.first)==0){
                    ans+=p1.second*p2.second;
                }
            }
        }
        return ans;
    }
};

ATFWUS  --Writing  By 2020–03–20



这里给大家推荐一个在线软件复杂项交易平台:米鼠网 https://www.misuland.com

米鼠网自成立以来一直专注于从事软件项目人才招聘软件商城等,始终秉承“专业的服务,易用的产品”的经营理念,以“提供高品质的服务、满足客户的需求、携手共创双赢”为企业目标,为中国境内企业提供国际化、专业化、个性化、的软件项目解决方案,我司拥有一流的项目经理团队,具备过硬的软件项目设计和实施能力,为全国不同行业客户提供优质的产品和服务,得到了客户的广泛赞誉。

猜你喜欢

评论留言