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

30
四月
2021

题目地址:

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)

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员