网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

【Leetcode】1497. Check If Array Pairs Are Divisible by k

2021/4/30 5:54:39 人评论

题目地址: https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k/ 给定一个偶数长度的数组AAA,其长度nnn,再给定一个正整数kkk,问AAA是否能整理成n/2n/2n/2个数对,使得每个数对的和能被kkk整除。…

题目地址:

https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k/

给定一个偶数长度的数组 A A A,其长度 n n n,再给定一个正整数 k k k,问 A A A是否能整理成 n / 2 n/2 n/2个数对,使得每个数对的和能被 k k k整除。

求一下每个数对 k k k的余数并计数,只要余数相加为 k k k的个数两两相等即可。注意余数为 0 0 0的要特判。代码如下:

public class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] cnt = new int[k];
        for (int x : arr) {
            cnt[(x % k + k) % k]++;
        }
        
        if (cnt[0] % 2 != 0) {
            return false;
        }
        
        for (int i = 1, j = k - 1; i < j; i++, j--) {
            if (cnt[i] != cnt[j]) {
                return false;
            }
        }
        
        return true;
    }
}

时间复杂度 O ( n ) O(n) O(n),空间 O ( k ) O(k) O(k)

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?