class Solution {
public:
bool canArrange(vector<int>& arr, int k) {
}
};
1497. 检查数组对是否可以被 k 整除
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 True ；否则，返回 False 。
示例 1：
输入：arr = [1,2,3,4,5,10,6,7,8,9], k = 5 输出：true 解释：划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10) 。
示例 2：
输入：arr = [1,2,3,4,5,6], k = 7 输出：true 解释：划分后的数字对为 (1,6),(2,5) 以及 (3,4) 。
示例 3：
输入：arr = [1,2,3,4,5,6], k = 10 输出：false 解释：无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。
提示：
arr.length == n1 <= n <= 105n 为偶数-109 <= arr[i] <= 1091 <= k <= 105原站题解
cpp 解法, 执行用时: 140 ms, 内存消耗: 68 MB, 提交时间: 2023-06-16 17:47:04
class Solution {
public:
bool canArrange(vector<int>& arr, int k) {
unordered_map<int, int> mod;
for (int num: arr) {
++mod[(num % k + k) % k];
}
for (auto [t, occ]: mod) {
if (t > 0 && (!mod.count(k - t) || mod[k - t] != occ)) {
return false;
}
}
return mod[0] % 2 == 0;
}
};
python3 解法, 执行用时: 148 ms, 内存消耗: 31.7 MB, 提交时间: 2023-06-16 17:46:09
class Solution:
def canArrange(self, arr: List[int], k: int) -> bool:
mod = collections.Counter(num % k for num in arr)
for t, occ in mod.items():
if t > 0 and (k - t not in mod or mod[k - t] != occ):
return False
return mod[0] % 2 == 0
java 解法, 执行用时: 34 ms, 内存消耗: 55.8 MB, 提交时间: 2023-06-16 17:45:47
class Solution {
public boolean canArrange(int[] arr, int k) {
Map<Integer, Integer> mod = new HashMap<Integer, Integer>();
for (int num : arr) {
mod.put((num % k + k) % k, mod.getOrDefault((num % k + k) % k, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : mod.entrySet()) {
int t = entry.getKey(), occ = entry.getValue();
if (t > 0 && mod.getOrDefault(k - t, 0) != occ) {
return false;
}
}
return mod.getOrDefault(0, 0) % 2 == 0;
}
}
java 解法, 执行用时: 3 ms, 内存消耗: 55.5 MB, 提交时间: 2023-06-16 17:45:36
class Solution {
public boolean canArrange(int[] arr, int k) {
int[] mod = new int[k];
for (int num : arr) {
++mod[(num % k + k) % k];
}
for (int i = 1; i + i < k; ++i) {
if (mod[i] != mod[k - i]) {
return false;
}
}
return mod[0] % 2 == 0;
}
}
python3 解法, 执行用时: 96 ms, 内存消耗: 29.9 MB, 提交时间: 2023-06-16 17:45:20
class Solution:
def canArrange(self, arr: List[int], k: int) -> bool:
mod = [0] * k
for num in arr:
mod[num % k] += 1
if any(mod[i] != mod[k - i] for i in range(1, k // 2 + 1)):
return False
return mod[0] % 2 == 0
cpp 解法, 执行用时: 88 ms, 内存消耗: 60.3 MB, 提交时间: 2023-06-16 17:44:42
class Solution {
public:
bool canArrange(vector<int>& arr, int k) {
vector<int> mod(k);
for (int num: arr) {
++mod[(num % k + k) % k];
}
for (int i = 1; i + i < k; ++i) {
if (mod[i] != mod[k - i]) {
return false;
}
}
return mod[0] % 2 == 0;
}
};