数组能形成多少数对【LC2341】
给你一个下标从 0 开始的整数数组
nums。在一步操作中，你可以执行以下步骤：
- 从
nums选出 两个相等的 整数- 从
nums中 移除这两个整数，形成一个 数对- 请你在
nums上多次执行此操作直到无法继续执行。返回一个下标从 0 开始、长度为
2的整数数组answer作为答案，其中answer[0]是形成的数对数目，answer[1]是对nums尽可能执行上述操作后剩下的整数数目。
哈希表
- 思路：使用哈希表记录某个数字在这之前是否存在，然后遍历每一个数字，如果存在那么可以从
nums中移除这两个整数，形成一个 数对；如果不存在那么将哈希表赋值为true。那么剩下的数字为数组长度-2*数对数目
实现
class Solution { public int[] numberOfPairs(int[] nums) { int n = nums.length; boolean[] flag = new boolean[101]; int[] res = new int[2]; for (int num : nums){ if (flag[num]){ res[0]++; flag[num] = false; }else{ flag[num] = true; } } res[1] = n - 2 * res[0]; return res; } }
复杂度
时间复杂度：O ( n ) ，n为数组长度
空间复杂度：O ( C ) ，C为字符集大小，本题中为101
排序
- 思路：将数组排序，从数组第一个元素开始遍历，如果
nums[i]==nums[i+1]，那么可以形成一个数对，指针向后移动两个；否则后移一位 - 实现
class Solution { public int[] numberOfPairs(int[] nums) { int n = nums.length; int[] res = new int[2]; Arrays.sort(nums); int i = 0; while (i < n - 1){ if (nums[i] == nums[i + 1]){ res[0]++; i += 2; }else{ i++; } } res[1] = n - 2 * res[0]; return res; } }
复杂度
时间复杂度：O ( n l o g n ) ，n为数组长度
空间复杂度：O ( 1 )
