上海网站建设咨询,个人可以做建站网站么,教育学会网站建设项目,山西公司网站开发文章目录题目描述题目链接题目难度——中等方法一#xff1a;排序双指针代码/Python代码/C方法二代码/Python总结题目描述 这是前天周赛的第二题。 统计公平数对的数目 - 给你一个下标从 0 开始、长度为 n 的整数数组 nums #xff0c;和两个整数 lower 和 upper #xff0c…
文章目录题目描述题目链接题目难度——中等方法一排序双指针代码/Python代码/C方法二代码/Python总结题目描述 这是前天周赛的第二题。 统计公平数对的数目 - 给你一个下标从 0 开始、长度为 n 的整数数组 nums 和两个整数 lower 和 upper 返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况则认为它是一个 公平数对
0 i j n且lower nums[i] nums[j] upper 示例 1
输入nums [0,1,7,4,4,5], lower 3, upper 6 输出6 解释共计 6 个公平数对(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。
示例 2
输入nums [1,7,9,2,5], lower 11, upper 11 输出1 解释只有单个公平数对(2,3) 。 提示
1 nums.length 105nums.length n-109 nums[i] 109-109 lower upper 109
题目链接
题目难度——中等
方法一排序双指针 题目说需要统计公平数对的数目而重点在于这个数目一开始可能容易被误导将重点放在数对的下标ij上面仔细想想会发现我们只需要统计不同的数目就行不用在乎具体的下标。所以我们可以先将数组排序然后使用双指针经过两次遍历第一次我们统计一下满足上界upper的数对数目第二次我们统计满足下界lower的数对数目。 具体的第一次遍历时两个指针一前一后让p2n-1p10如果两个数相加大于upper我们就将p2左移一个位置直到两个数相加upper则此时从p1到p2之间的数两两之和都会upper也就有p2-p1个数对满足条件然后再将p1右移继续判断直到p1与p2相遇。第一次遍历时我们只找到了满足上界的下标对所以我们还要一次类似的遍历来减去多算的小于下界的数对。
代码/Python
class Solution:def countFairPairs(self, nums: List[int], lower: int, upper: int) - int:nums.sort()n len(nums)res 0p1, p2 0, n - 1while p1 p2:if nums[p1] nums[p2] upper:p2 - 1else:res p2 - p1p1 1p1, p2 0, n - 1while p1 p2:if nums[p1] nums[p2] lower:res - p2 - p1p1 1else:p2 - 1return res代码/C
class Solution {
public:long long countFairPairs(vectorint nums, int lower, int upper) {long long res 0;int p1, p2, n;sort(nums.begin(), nums.end());n nums.size();p1 0;p2 n - 1;while(p1 p2){if(nums[p1] nums[p2] upper){p2--;}else{res p2 - p1;p1;}}p1 0;p2 n - 1;while(p1 p2){if(nums[p1] nums[p2] lower){res - p2 - p1;p1;}else{p2--;}}return res;}
};方法二 前面既然已经排好序了那么我们可以想想是否可以再利用这个有序的性质比如二分查找。利用二分查找来加速找到满足条件的下标对实质上也是方法一的思路。这里贴一个灵茶大佬的题解灵茶大佬
代码/Python
class Solution:def countFairPairs(self, nums: List[int], lower: int, upper: int) - int:nums.sort()n len(nums)res 0for i, x in enumerate(nums):r bisect_right(nums, upper - x, 0, i)l bisect_left(nums, lower - x, 0, i)res r - lreturn res总结 方法一时间主要在前面排序上O(NlogN)后面遍历是O(N)所以总的复杂度是(NlogN)空间复杂度 O(1) 方法二在遍历里面有二分所以应该是O(N·logN)空间是O(1)。
