单页网站 产品放哪,wordpress style不更新,厦门网络推广专员,58同城最新消息招聘给你一个整数数组 hours#xff0c;表示以 小时 为单位的时间#xff0c;返回一个整数#xff0c;表示满足 i j 且 hours[i] hours[j] 构成 整天 的下标对 i, j 的数目。
整天 定义为时间持续时间是 24 小时的 整数倍 。
例如#xff0c;1 天是 24 小时#xff0c…给你一个整数数组 hours表示以 小时 为单位的时间返回一个整数表示满足 i j 且 hours[i] hours[j] 构成 整天 的下标对 i, j 的数目。
整天 定义为时间持续时间是 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(vectorint hours) {int len hours.size();int ret0;for (int i0; ilen; i){for (int ji1; jlen; 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(vectorint hours) {int len hours.size();vectorvectorint vec(24);for (int i0; ilen; i){int mod hours[i]%24;vec[mod].push_back(hours[i]);}int ans0;for (int i1; i12; 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(vectorint hours) {int len hours.size();mapint, int ma;for (int i0; ilen; i){ma[hours[i]%24];}int ma0ma[0], ma12ma[12];int ans ma0*(ma0-1)/2;ans ma12*(ma12-1)/2;for (int i1; i12; i){ans ma[i]*ma[24-i];}return ans;}
};
思路与之前一致只是少存了没用的数了顺便这里的map完全可以用一个数组代替我只是太久没写代码了用下map熟悉一下而已
时间复杂度还是O(n)但空间复杂度降到了O(1)。
这应该就是最终版了至少我想不到其他的优化方法了
翻了下力扣的题解我又找到了一个优化方法。其实也不算优化吧因为时空复杂度都不变只不过也许可能大概常数因子会稍微小一点因为把乘法换成了加法也少了一次循环但多了取余
class Solution {
public:int countCompleteDayPairs(vectorint 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的时候就会数组越界了。而且两个加法的顺序也不能换不然就多算了
