这是悦乐书的第 254 次更新, 第 267 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 121 题(顺位题号是 532). 给定一个整数数组和一个整数 k, 您需要找到数组中唯一的 k-diff 对的数量. 这里 k-diff 对被定义为整数对(i,j), 其中 i 和 j 都是数组中的数字, 它们的绝对差是 k. 例如:
输入:[3,1,4,1,5],k = 2
输出: 2
说明: 数组中有两个 2-diff 对,(1,3)和(3,5). 虽然我们在输入中有两个 1, 但我们应该只返回唯一对的数量.
输入:[1,2,3,4,5],k = 1
输出: 4
说明: 数组中有四个 1-diff 对,(1,2),(2,3),(3,4)和(4,5).
输入:[1,3,1,5,4],k = 0
输出: 1
说明: 数组中有一个 0-diff 对,(1,1).
注意:
对 (i,j) 和(j,i)计为同一对.
数组的长度不会超过 10,000.
给定输入中的所有整数都属于以下范围:[-1e7, 1e7].
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
暴力解法. 先排序, 然后使用两层循环, 计算不同元素的绝对值, 如果等于 k, 次数就加 1. 在外面第一层循环那里, 如果前后元素相同, 就跳过当前循环, 进行下一次循环. 在内层循环那里同样做了类似的判断, 排除重复计算.
此解法的时间复杂度是 O(n^2), 空间复杂度是 O(1).
- public int findPairs(int[] nums, int k) {
- if (nums == null || nums.length == 0 || k <0) {
- return 0;
- }
- Arrays.sort(nums);
- int count = 0;
- for (int i=0; i<nums.length; i++) {
- int n = nums[i];
- if (i>= 1 && nums[i-1] == nums[i]) {
- continue;
- }
- for (int j=i+1; j<nums.length; j++) {
- if (j>= i+2 && nums[j-1] == nums[j]) {
- continue;
- }
- if (Math.abs(n - nums[j]) == k) {
- count++;
- }
- }
- }
- return count;
- }
03 第二种解法
第一种解法时间复杂度太高了, 得降低点. 第一种解法, 我们是做减法, 求绝对值, 来判断是否等于 k, 我们也可以做加法, 拿当前元素加上 k, 然后看新元素是否存在于数组中. 同时还要考虑重复的计算数据, 因此参与计算的元素是唯一的, 对此我们可以使用 HashMap, 已元素值作为 key, 该元素值出现次数为 value. 遍历 key, 如果 key 加上 k 后的值存在于 map 中, 次数加 1, 另外如果 k 为 0 的时候, 只需要判断每个 key 所对应的 value 是否大于等于 2 即可.
此解法的时间复杂度是 O(n), 最坏情况也可能是 O(n^2), 空间复杂度是 O(n).
- public int findPairs2(int[] nums, int k) {
- if (nums == null || nums.length == 0 || k <0) {
- return 0;
- }
- Map<Integer,Integer> map = new HashMap<Integer,Integer>();
- for (int n : nums) {
- map.put(n, map.getOrDefault(n, 0)+1);
- }
- int count = 0;
- if (k == 0) {
- for (Integer key: map.keySet()) {
- if (map.get(key)>= 2) {
- count++;
- }
- }
- } else {
- for (Integer key: map.keySet()) {
- if (map.containsKey(key+k)) {
- count++;
- }
- }
- }
- return count;
- }
04 第三种解法
对于第二种解法, 还可以将判断放在循环体里面.
- public int findPairs3(int[] nums, int k) {
- if (nums == null || nums.length == 0 || k <0) {
- return 0;
- }
- Map<Integer,Integer> map = new HashMap<Integer,Integer>();
- for (int n : nums) {
- map.put(n, map.getOrDefault(n, 0)+1);
- }
- int count = 0;
- for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
- if (k == 0) {
- if (entry.getValue()>= 2) {
- count++;
- }
- } else {
- if (map.containsKey(entry.getKey()+k)) {
- count++;
- }
- }
- }
- return count;
- }
05 第四种解法
使用 HashSet. 使用两个 HashSet, 同样分为两种情况: k 等于 0 和 K 不等于 0.
如果 k 等于 0 时, 对数组进行遍历, 如果当前元素不存在于 set1 中, 就添加进 set1, 如果存在 set1 中, 就去判断是否存在于 set2 中, 如果不存在, 次数就加 1, 并将元素添加进 set2 中.
如果 k 不等于 0, 遍历数组, 将当前元素添加进 set1, 将当前元素加上 k 后再添加进 set2, 然后使用 retainAll 方法, 将 set1 中不包含 set2 元素的元素剔除掉(也就是两 set 的交集), 最后 count 等于 set1 中元素的个数.
- public int findPairs4(int[] nums, int k) {
- if (nums == null || nums.length == 0 || k <0) {
- return 0;
- }
- Set<Integer> set1 = new HashSet<Integer>();
- Set<Integer> set2 = new HashSet<Integer>();
- int count = 0;
- if (k == 0) {
- for (int n : nums) {
- if (!set1.contains(n)) {
- set1.add(n);
- } else {
- if (!set2.contains(n)){
- count++;
- }
- set2.add(n);
- }
- }
- } else {
- for (int n : nums) {
- set1.add(n);
- set2.add(n + k);
- }
- set1.retainAll(set2);
- count = set1.size();
- }
- return count;
- }
06 第五种解法
使用双指针. 还是先将数据排序, 定义左右两个指针, 分别从 0 开始, 如果左右指针相等, 说明是循环的第一次或者重复了, 就需要将右指针往后移动一位. 如果左指针所指向元素加上 k 后等于右指针的元素, 那么次数加 1, 接着要判断, 如果右指针所指向位置后面的元素和当前元素相等, 那么右指针继续往后移动. 如果左指针所指向元素加上 k 后小于右指针的元素, 说明左边的元素小了, 左指针向前移动. 如果左指针所指向元素加上 k 后大于右指针的元素, 说明右边的元素小了, 右指针向前移动.
此解法的时间复杂度是 O(n log(n)), 空间复杂度是 O(1).
- public int findPairs5(int[] nums, int k) {
- if (nums == null || nums.length == 0 || k <0) {
- return 0;
- }
- Arrays.sort(nums);
- int count = 0;
- int start = 0, end = 0;
- while (end < nums.length) {
- if (start == end) {
- end++;
- } else if (nums[start] + k == nums[end]) {
- count++;
- while (end + 1 < nums.length && nums[end] == nums[end + 1]) {
- end++;
- }
- end++;
- } else if (nums[start] + k < nums[end]) {
- start++;
- } else if (nums[start] + k> nums[end]) {
- end++;
- }
- }
- return count;
- }
07 小结
此题的测试用例中, k 出现了负值, 所以在特殊情况判断中, 还需要判断 k 小于 0, 这也是本题不严谨的一个地方.
算法专题目前已日更超过三个月, 算法题文章 121 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!