leetcode-1497. 检查数组对是否可以被 k 整除刷题笔记（c++）

矫情吗；* 2023-02-22 05:13 23阅读 0赞

#### 写在前面 ####

*  难度：中等
 *  数学题，余数问题

#### 题目详情 ####

给你一个整数数组 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
    
    提示：
    
    arr.length == n
    1 <= n <= 10^5
    n 为偶数
    -10^9 <= arr[i] <= 10^9
    1 <= k <= 10^5

#### ac代码 ####

*  解题思想
    
     *  对数组元素逐个求余
        
         *  余数为负数时，余数+k再取余，并通过`vector<int>`数组记录该余数且统计频次
     *  `数组可分条件`
        
         *  余数为1和k-1、2和k-2等组合频次相等
         *  余数为0的频次为偶数

class Solution
    {
        
    public:
        bool canArrange(vector<int>& arr, int k)
        {
        
            vector<int> freq(k, 0);
            for(auto c : arr)
                freq[(c%k+k)%k]++;
            if(freq[0]%2 != 0)
                return false;
            for(int i=1; i<=k/2; i++)
                if(freq[i] != freq[k-i])
                    return false;
            return true;
        }
    };

*  知识点补充
    
     *  multiset 集合自带排序
     *  与set集合最大区别就是，set中元素具有唯一性，multiset 可以容纳多个相同元素
 *  测试代码

#include<iostream>
    #include<set>
    using namespace std;
    
    int main() {
        
    	multiset<int> myMultiSet = {
         10,20,30,10,100,70,30,40 };
    	cout << myMultiSet.size() << "-" << endl;
    	cout << "正向迭代器遍历容器：";
    	for (auto it = myMultiSet.begin(); it != myMultiSet.end(); ++it) {
        
    		cout << *it << " ";
    	}
    	return 0;
    }
    
    // 输出结果
    // 8-
    // 正向迭代器遍历容器：10 10 20 30 30 40 70 100

*  参考文章
    
     *  [LeetCode 1497. 检查数组对是否可以被 k 整除（余数配对）][LeetCode 1497. _ k]
     *  [C++ STL容器之multiset][C_ STL_multiset]

[LeetCode 1497. _ k]: https://blog.csdn.net/qq_21201267/article/details/106996448?utm_medium=distribute.pc_relevant_t0.none-task-blog-OPENSEARCH-1.nonecase&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-OPENSEARCH-1.nonecase
[C_ STL_multiset]: https://blog.csdn.net/qq_41855420/article/details/89765258