淘先锋技术网

首页 1 2 3 4 5 6 7

2023-08-23每日一题

一、题目编号

1782. 统计点对的数目

二、题目链接

点击跳转到题目位置

三、题目描述

给你一个无向图,无向图由整数 n ,表示图中节点的数目,和 edges 组成,其中 edges[i] = [ui, vi] 表示 ui 和 vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。

第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目:

  • a < b
  • cnt 是与 a 或者 b 相连的边的数目,且 cnt 严格大于 queries[j] 。

请你返回一个数组 answers ,其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。

请注意,图中可能会有 重复边

示例 1:
在这里插入图片描述
示例 2:
在这里插入图片描述
提示:

  • 2 <= n <= 2 * 104
  • 1 <= edges.length <= 105
  • 1 <= ui, vi <= n
  • ui != vi
  • 1 <= queries.length <= 20
  • 0 <= queries[j] < edges.length

四、解题代码

class Solution {
    unordered_map<int, int> cnt;

    int find(int left, int right, vector<int>& arr, int num){
        int ans = -1; 
        while(left <= right){
            int mid = ((right - left) >> 1) + left;
            if(arr[mid] > num){
                ans = mid;
                right = mid - 1;                
            } else{
                left = mid + 1; 
            }
        }
    return ans;
    }

public:
    void swap(int &x, int &y){
        int temp = x;
        x = y;
        y = temp;
    }
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        vector<int> degree(n);
        for(int i = 0; i < edges.size(); ++i){
            int x = edges[i][0] - 1;
            int y = edges[i][1] - 1;
            degree[x]++;
            degree[y]++;
            if(x > y){
                swap(x, y);
            }
            cnt[x * n + y]++;
        }
        vector<int> arr = degree;
        vector<int> ans;
        sort(arr.begin(), arr.end());        
        for(int i = 0; i < queries.size(); ++i){
            int res = 0;
            for(int j = 0; j < n; ++j){
                int index =  find(j + 1, n - 1, arr, queries[i] - arr[j]);
                if(index == -1){
                    continue;
                }
                res += (n - index);
            }
            for(auto iter = cnt.begin(); iter != cnt.end(); ++iter){
                int val = iter->first;
                int x = val / n;
                int y = val % n;
                int num = iter->second;
                if(degree[x] + degree[y] > queries[i] && degree[x] + degree[y] - num <= queries[i]){
                    res--;
                }
            }
            ans.push_back(res);
        }
    return ans;
    }
};

五、解题思路

(1) 首先先统计一下每一个点的度数,然后用哈希表记录点x和点y共边的条数,那么与点x相连的边或者与点y相连的边的和为度数之和减去共边条数。

(2) 然后将度数在放在一个新的数组arr中,并且从小到大排序。

(3) 为了方便计算,将点的下标由1 ~ n改变成0 ~ n - 1。

(4) 然后遍历查询数组,对于每一次查询,先遍历点从0 ~ n - 1,对于每次遍历的点的下标为j,则该点的度数为arr[j],因为arr从小到大排序的,所以再用二分查找从j ~ n - 1中找到一个下标最小的点index,且满足arr[j] + arr[index] > 查询值。那么此时数对的数量为n - index,加上即可。

(5) 最后不要忘记减去共边的情况。如果度数之和满足条件但是减去共边之后不满足条件,就需要剔除。

(6) 最后返回结果数组即可。