【每日一题Day120】LC2341数组能形成多少数对 | 哈希表 排序

数组能形成多少数对【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(nlogn)$，n为数组长度
    • 空间复杂度：$O(1)$