给你一个整数数组 hours,表示以 小时 为单位的时间,返回一个整数,表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 ij 的数目。

整天 定义为时间持续时间是 24 小时的 整数倍 

例如,1 天是 24 小时,2 天是 48 小时,3 天是 72 小时,以此类推

这个题目特别简单,因为数据范围只有100,直接两重循环,完全不存在超时的问题,一个枚举i,一个枚举j,然后判断是否和为24的倍数就可以了。不过因为hours数组的最大值是1e9,还有求和,所以为了保险起见避免爆int,我用了long long

时间复杂度O(n*n), 空间复杂度O(1)。

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int len = hours.size();
        int ret=0;
        for (int i=0; i<len; i++)
        {
            for (int j=i+1; j<len; j++)
            {
                long long ans = hours[i]+hours[j];
                if (ans % 24 == 0)
                {
                    ret++;
                }
            }
        }
        return ret;
    }
};

 前面只是上课前赶时间写的,而很明显这个题目应该还有可以优化的地方,平方的复杂度还是有点高了。那么有什么办法可以优化一下呢?可以这样想,我们的i已经确定了,那么要找的j就是固定加起来是24的倍数的。那是不是可以想办法记录一下每个数和哪些数加起来是24的倍数呢。当然可以,给每个数对24取余一下就可以了,而和它组成的24倍数的就是取余后和为24的。这一点应该能够理解。这样就得到了一个改进版的代码了,实际上这也就是哈希了

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int len = hours.size();
        vector<vector<int> > vec(24);
        for (int i=0; i<len; i++)
        {
            int mod = hours[i]%24;
            vec[mod].push_back(hours[i]);
        }
        int ans=0;
        for (int i=1; i<12; i++)
        {
            ans += (vec[i].size())*(vec[24-i].size());
        }
        int mod0 = vec[0].size(), mod12 = vec[12].size();
        ans += mod0*(mod0-1)/2;
        ans += mod12*(mod12-1)/2;
        return ans;
    }
};

取余为0和取余为12的需要特判一下,因为和它们配对的数的取余值就是自己。

这样就把两重循环变成了一重循环,但增加了一个vec数组用来记录每个数取余后所在的位置。

时间复杂度O(n), 空间复杂度O(n)。

那么,还有办法可以继续优化吗?时间复杂度肯定是降不下去了,毕竟不管怎么改,总得遍历一次吧。但空间复杂度说不定还可以优化一下。

确实可以,我们可以注意到,我们虽然在vec里把每个数都存了起来,但实际上我们并没有用到它们。我们只是用到了数量。那么我们完全可以选择不存这些数,而只记录一下取余后的值的数量。

这样我们就得到了下一版的代码了

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int len = hours.size();
        map<int, int> ma;
        for (int i=0; i<len; i++)
        {
            ma[hours[i]%24]++;
        }
        int ma0=ma[0], ma12=ma[12];
        int ans = ma0*(ma0-1)/2;
        ans += ma12*(ma12-1)/2;
        for (int i=1; i<12; i++)
        {
            ans += ma[i]*ma[24-i];
        }
        return ans;
    }
};

思路与之前一致,只是少存了没用的数了,顺便这里的map完全可以用一个数组代替,我只是太久没写代码了,用下map熟悉一下而已

时间复杂度还是O(n),但空间复杂度降到了O(1)。

这应该就是最终版了,至少我想不到其他的优化方法了

翻了下力扣的题解,我又找到了一个优化方法。其实也不算优化吧,因为时空复杂度都不变,只不过也许可能大概常数因子会稍微小一点,因为把乘法换成了加法,也少了一次循环,但多了取余

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int ans = 0;
        int cnt[24];
        memset(cnt, 0, sizeof(cnt));//也许换成循环会更快一点点?
        for (int h : hours)
        {
            int mod = h%24;
            ans += cnt[(24-mod)%24];
            cnt[mod]++;
        }
        return ans;
    }
};

特别提醒一句,cnt[(24-mod)%24]里面的取余是必不可少的,不然mod为0的时候就会数组越界了。而且两个加法的顺序也不能换,不然就多算了

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部