LeetCode 1497. 检查数组对是否可以被 k 整除
原题链接
中等
作者:
胡歌-此生不换
,
2022-09-25 19:36:34
,
所有人可见
,
阅读 145
思路:
- 用
unordered_map<int, int> cnt
; 存储 nums 数组里面的数 % k 的余数;
- 所以 cnt 的 first 元素存储的是余数,余数的范围在 [0, k - 1]; (注意 nums 数组里面有负数哦)
对于负数 % 正数 k,要得到正数就 (x % k + k) % k;
对于正数 % 正数 k,要得到正数就 x % k;
- 所以余数是 0 的和余数是 0 的匹配,所以要求
cnt[0] % 2 == 0
才对;
- 余数是 1 的和余数是 k - 1 的匹配,余数是 2 和余数是 k - 2 的匹配......; 所以要求
cnt[i] == cnt[k - i]
才对;
时间复杂度:O(n)
代码实现:
class Solution {
public:
bool canArrange(vector<int>& nums, int k)
{
// if(n == 1) return false;
unordered_map<int, int> cnt; // cnt[(x % k + k) % k] 存储的是 nums[i] % k 余数的个数 (要的余数要是正数哦)
int n = nums.size();
for(auto x: nums)
cnt[(x % k + k) % k]++; // 负数 % 正数,在 c++ 里面是负数哦
if(cnt[0] % 2 != 0) return false;
for(int i = 1; i < k; i++)
{
while(cnt[i])
{
cnt[i]--;
if(cnt[k - i] <= 0) return false;
cnt[k - i]--;
}
}
// 下面的做法,可能 cnt[i] 和 cnt[k - i] 的个数不相等
// for(int i = 1; i < k - i; i++)
// if((cnt[i] + cnt[k - i]) % 2 != 0) return false;
// cnt[i] != cnt[k - i] 这个条件就可以了(关键是要一一对应匹配)
// for(int i = 1; i < k - i; i++)
// if(cnt[i] != cnt[k - i]) return false;
return true;
}
};