给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：
- 从
nums 选出 两个 相等的 整数
- 从
nums 中移除这两个整数，形成一个 数对
请你在 nums 上多次执行此操作直到无法继续执行。
返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，其中 __answer[0] __
是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。
示例 1：
**输入：** nums = [1,3,2,1,3,2,2]
**输出：** [3,1]
**解释：**
nums[0] 和 nums[3] 形成一个数对，并从 nums 中移除，nums = [3,2,3,2,2] 。
nums[0] 和 nums[2] 形成一个数对，并从 nums 中移除，nums = [2,2,2] 。
nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [2] 。
无法形成更多数对。总共形成 3 个数对，nums 中剩下 1 个数字。
示例 2：
**输入：** nums = [1,1]
**输出：** [1,0]
**解释：** nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [] 。
无法形成更多数对。总共形成 1 个数对，nums 中剩下 0 个数字。
示例 3：
**输入：** nums = [0]
**输出：** [0,1]
**解释：** 无法形成数对，nums 中剩下 1 个数字。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
方法一：哈希表
思路
遍历一次数组，用一个哈希表保存元素个数的奇偶性，偶数为 false，奇数则为 true。每遇到一个元素，则将奇偶性取反，若取反完后为偶数个，则表明在上次偶数个之后又遇到了两个该元素，可以形成一个数对。最后返回一个数组，第一个元素是数对数，第二个元素是数组长度减去数对数的两倍。
代码
[sol1-Python3]1
2
3
4
5
6
7
8
9
| class Solution:
def numberOfPairs(self, nums: List[int]) -> List[int]:
cnt = defaultdict(bool)
res = 0
for num in nums:
cnt[num] = not cnt[num]
if not cnt[num]:
res += 1
return [res, len(nums) - 2 * res]
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int[] numberOfPairs(int[] nums) {
Map<Integer, Boolean> cnt = new HashMap<Integer, Boolean>();
int res = 0;
for (int num : nums) {
cnt.put(num, !cnt.getOrDefault(num, false));
if (!cnt.get(num)) {
res++;
}
}
return new int[]{res, nums.length - 2 * res};
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Solution {
public int[] NumberOfPairs(int[] nums) {
IDictionary<int, bool> cnt = new Dictionary<int, bool>();
int res = 0;
foreach (int num in nums) {
if (cnt.ContainsKey(num)) {
cnt[num] = !cnt[num];
} else {
cnt.Add(num, true);
}
if (!cnt[num]) {
res++;
}
}
return new int[]{res, nums.Length - 2 * res};
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<int> numberOfPairs(vector<int>& nums) {
unordered_map<int, bool> cnt;
int res = 0;
for (int num : nums) {
if (cnt.count(num)) {
cnt[num] = !cnt[num];
} else {
cnt[num] = true;
}
if (!cnt[num]) {
res++;
}
}
return {res, (int)nums.size() - 2 * res};
}
};
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| typedef struct {
int key;
bool val;
UT_hash_handle hh;
} HashItem;
HashItem *hashFindItem(HashItem **obj, int key) {
HashItem *pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry);
return pEntry;
}
bool hashAddItem(HashItem **obj, int key, bool val) {
if (hashFindItem(obj, key)) {
return false;
}
HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
pEntry->key = key;
pEntry->val = val;
HASH_ADD_INT(*obj, key, pEntry);
return true;
}
bool hashSetItem(HashItem **obj, int key, bool val) {
HashItem *pEntry = hashFindItem(obj, key);
if (!pEntry) {
hashAddItem(obj, key, val);
} else {
pEntry->val = val;
}
return true;
}
bool hashGetItem(HashItem **obj, int key, bool defaultVal) {
HashItem *pEntry = hashFindItem(obj, key);
if (!pEntry) {
return defaultVal;
}
return pEntry->val;
}
void hashFree(HashItem **obj) {
HashItem *curr = NULL, *tmp = NULL;
HASH_ITER(hh, *obj, curr, tmp) {
HASH_DEL(*obj, curr);
free(curr);
}
}
int* numberOfPairs(int* nums, int numsSize, int* returnSize) {
HashItem *cnt = NULL;
int res = 0;
for (int i = 0; i < numsSize; i++) {
if (hashFindItem(&cnt, nums[i])) {
hashSetItem(&cnt, nums[i], !hashGetItem(&cnt, nums[i], false));
} else {
hashAddItem(&cnt, nums[i], true);
}
if (!hashGetItem(&cnt, nums[i], false)) {
res++;
}
}
hashFree(&cnt);
int *ans = (int *)malloc(sizeof(int) * 2);
ans[0] = res;
ans[1] = numsSize - 2 * res;
*returnSize = 2;
return ans;
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
| var numberOfPairs = function(nums) {
const cnt = new Map();
let res = 0;
for (const num of nums) {
cnt.set(num, !(cnt.get(num) || false));
if (!cnt.get(num)) {
res++;
}
}
return [res, nums.length - 2 * res];
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
| func numberOfPairs(nums []int) []int {
cnt := map[int]bool{}
res := 0
for _, num := range nums {
cnt[num] = !cnt[num]
if !cnt[num] {
res++
}
}
return []int{res, len(nums) - 2*res}
}
|
复杂度分析
