392,检查数组对是否可以被 k 整除
Some day, this is all going to end.
总有一天,一切都会雨过天晴。
问题描述
给你一个整数数组 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整除的条件。
示例 4:
输入:arr = [-10,10], k = 2
输出:true
示例 5:
输入:arr = [-1,1,-2,2,-3,3,-4,4], k = 3
输出:true
问题分析
这道题问的实际上是把数组中的元素每两个分为一组,总共分为n/2组,然后确保每组都能被k整除,这样结果才会返回true,否则返回false。
其实这里面有个数学问题,假如有两组数据(a,b)和(c,d)他们都能被k整除,也就是说(a+b)%k=0,并且(c+d)%k=0;如果(a+c)%k=0,那么(b+d)%k=0肯定也是成立的。(这里的所有字母都是整数)
我们可以证明一下
假如a+b=m*k,并且c+d=n*k。
如果a+c=t*k;
那么b+d=(m*k-a)+(n*k-c)
=(m+n)*k-(a+c)
=(m+n)*k-t*k
=(m+n-t)*k(这里能被k整除)
所以我们可以证明b+d也一定是可以被k整除的。
举个例子,比如(3,5),(7,9)都能被4整除,如果(3+9)能被4整除,那么(5+7)也一定能被4整除。
有了上面的证明我们再来看这道题,所以我们很容易想到暴力求解,我们使用两个指针,一个指针指向一个固定的元素,另一个指针从这个固定的元素下一个开始查找,如果找到就把这两个元素标记为删除,然后再继续查找……。如果没找到就直接返回false,我们以示例2为例来画个图看一下
最后我们再来看下代码部分
1public boolean canArrange(int[] arr, int k) {
2 int length = arr.length;
3 boolean[] visit = new boolean[arr.length];
4 for (int i = 0; i < length - 1; i++) {
5 if (visit[i])//数字被访问过了,就不能再用了
6 continue;
7 for (int j = i + 1; j < length; j++) {
8 if (visit[j])//数字被访问过了,就不能再用了
9 continue;
10 if ((arr[i] + arr[j]) % k == 0) {
11 //如果被找到了,我们就把他标记为已使用,
12 //下次就不会再用它了
13 visit[i] = visit[j] = true;
14 break;
15 }
16 }
17 if (!visit[i])//没找到匹配的直接返回false
18 return false;
19 }
20 return true;
21}
代码优化
我们来思考这样一个问题,如果a+b能被k整除,那么a和b分别对k求余的结果相加也一定能被k整除,即(a%k+b%k)%k=0。所以我们可以对上面数组中的元素分别对k求余。
即num=num%k,因为数组中可能会有负数,所以求余的结果也可能为负,这里为了计算方便,我们把求余的结果全部转化为非负数,大小在[0,k-1]中,包含0和k-1。所以计算公式是num=(num%k+k)%k
这样我们只需要计算余数相对应位置上的个数是否相等就可以了,举个例子,比如k是5,那么余数中1的个数必须和4的个数一样多,2的个数必须和3的个数一样多,这样才能匹配成功,否则直接返回false。还有一点是0的个数必须是偶数
比如余数中[1,2,1,3,4,1]由于2和3的个数都是1所以能组合成一组,但1的个数和4的个数不一致,所以只有一个能组合成功,另一对组合失败。最后我们再来看下代码
1public boolean canArrange(int[] arr, int k) {
2 int[] mod = new int[k];
3 //统计求余之后各余数的个数
4 for (int num : arr)
5 mod[(num % k + k) % k]++;
6 for (int i = 1; i < k / 2; ++i)
7 //如果对应的个数不匹配,直接返回false
8 if (mod[i] != mod[k - i])
9 return false;
10 //余数中0的个数必须是偶数
11 return mod[0] % 2 == 0;
12}
长按上图,识别图中二维码之后即可关注。
如果喜欢这篇文章就点个"在看"吧