leetcode
leetcode 1351 ~ 1400
检查数组对是否可以被 k 整除

检查数组对是否可以被 k 整除

难度:

标签:

题目描述

代码结果

运行时间: 76 ms, 内存: 29.4 MB


/*
 * 思路:
 * 1. 使用Java Stream计算每个元素对k取模的结果。
 * 2. 使用一个计数器数组count记录每个取模结果出现的次数。
 * 3. 使用Stream的forEach遍历计数器数组,检查是否存在满足条件的配对。
 *    - 对于取模结果为0的元素,数量必须是偶数。
 *    - 对于其他取模结果x,数量必须与取模结果k-x的数量相等。
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] count = new int[k];
        Arrays.stream(arr).forEach(num -> count[((num % k) + k) % k]++);
        if (count[0] % 2 != 0) return false;
        return IntStream.range(1, k / 2 + 1).allMatch(i -> count[i] == count[k - i]);
    }
}

解释

方法:

这个题解的思路是首先统计每个数字模 k 的结果出现的次数,然后检查是否存在一种分配方法使得每对数字的和都能被 k 整除。具体来说,对于每个非零的模数 i,必须有相同数量的数字模数为 k - i,这样它们才能配对组成和为 k 的倍数。另外,模数为 0 的数字数量必须是偶数,这样它们才能相互配对。

时间复杂度:

O(n + k)

空间复杂度:

O(k)

代码细节讲解

🦆
在您的解法中,为什么需要检查模数为0的数字数量必须是偶数?
模数为0的数字意味着这些数字直接是k的倍数。在配对这些数字时,只有两个同样是k的倍数的数字相加仍然是k的倍数。因此,为了确保所有这些模数为0的数字可以通过相互配对来组成k的倍数,它们的数量必须是偶数。如果是奇数,则会剩下一个无法配对的数字,导致无法满足题目要求。
🦆
如果数组中存在负数,这会影响模数的计算和最终结果吗?如何处理这种情况?
在Python中,负数进行取模运算可能得到负的模数。例如,-1 % k 得到的结果是 k-1 而不是 1。这可能会影响统计模数的准确性。为了处理这种情况,我们可以将负的模数转换为正的模数,即将计算模数的步骤修改为 `mod[(num % k + k) % k] += 1`。这样,不论正负数,都能统一到一个正确的模数区间内,保证计数的正确性。
🦆
在检查模数i和k-i的数量是否相等时,为什么只需遍历到k/2?遍历完整个数组会有什么不同的结果?
检查模数i和k-i的数量是否相等时,遍历到k/2是因为当你考虑一个模数i时,同时也在考虑与之配对的模数k-i。如果遍历超过k/2,那么将会重复检查已经考虑过的配对,因为对于任何i > k/2,其配对的k-i已经在之前的迭代中作为某个j < k/2的配对考虑过了。因此,遍历到k/2就足够了,完整遍历将导致不必要的重复检查。
🦆
您的解法中提到了`if any(mod[i] != mod[k - i] for i in range(1, k // 2 + 1))`,这里使用了`any`函数,请解释其作用和为何选择使用它?
在Python中,`any`函数用于检查传入的可迭代对象中是否至少有一个元素为True。在此代码中,它用于检查从1到k/2的所有模数i是否存在其数量与模数k-i的数量不相等的情况。如果存在这样的模数i,则`any`函数返回True,表示无法找到完全匹配的模数对来满足题目要求,从而函数返回False表示不可能按要求配对数组。使用`any`函数可以简洁地在找到第一个不符合条件的情况时立即结束检查,提高代码效率。

相关问题