北京市企业信用信息网,seo营销技巧,黄页软件app大全,惠州网站建设技术外包洛谷 P1102 A-B 数对 (Java)
传送门#xff1a;P1102 A-B 数对
题目#xff1a; A-B 数对
题目背景
出题是一件痛苦的事情#xff01;
相同的题目看多了也会有审美疲劳#xff0c;于是我舍弃了大家所熟悉的 AB Problem#xff0c;改用 A-B 了哈哈#xff01;
题目描…洛谷 P1102 A-B 数对 (Java)
传送门P1102 A-B 数对
题目 A-B 数对
题目背景
出题是一件痛苦的事情
相同的题目看多了也会有审美疲劳于是我舍弃了大家所熟悉的 AB Problem改用 A-B 了哈哈
题目描述
给出一串正整数数列以及一个正整数 C C C要求计算出所有满足 A − B C A - B C A−BC 的数对的个数不同位置的数字一样的数对算不同的数对。
输入格式
输入共两行。
第一行两个正整数 N , C N,C N,C。
第二行 N N N 个正整数作为要求处理的那串数。
输出格式
一行表示该串正整数中包含的满足 A − B C A - B C A−BC 的数对的个数。
样例 #1
样例输入 #1
4 1
1 1 2 3样例输出 #1
3提示
对于 75 % 75\% 75% 的数据 1 ≤ N ≤ 2000 1 \leq N \leq 2000 1≤N≤2000。
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2 \times 10^5 1≤N≤2×105 0 ≤ a i 2 30 0 \leq a_i 2^{30} 0≤ai230 1 ≤ C 2 30 1 \leq C 2^{30} 1≤C230。
2017/4/29 新添数据两组
分析
创建一个 HashMap map用于记录数组中每个数字的出现次数。
创建一个数组 a用于存储输入的整数数组。
定义cnt 用于记录满足条件的数对个数。
再次循环数组 a对于每个元素 a[i]
如果 HashMap 中存在键值为 a[i]c 的项则将其值加到 cnt 中。 输出 cnt即为满足条件的数对个数。
这个算法的时间复杂度为 O(N)其中 N 为数组长度。因为在第一个循环中构建了 HashMap而在第二个循环中通过查找 HashMap 进行计数每个查找操作的时间复杂度是 O(1)。因此总体的时间复杂度取决于循环次数即 O(N)。
代码
import java.util.*;public class Main{public static void main(String[] args) { Scanner sc new Scanner(System.in);int n sc.nextInt();int c sc.nextInt();MapInteger,Integer map new HashMap();int [] a new int [n];for(int i 0;i n;i) {int tt sc.nextInt();a[i] tt;map.compute(tt, (key, value) - (value null) ? 1 : value 1);}long cnt 0;for(int i 0;i n;i) {if(map.containsKey(a[i]c)) {cnt map.get(a[i]c);}}System.out.println(cnt);sc.close();}
}
