【算法leetcode】2341. 数组能形成多少数对（多种语言双百）

---

---

2341. 数组能形成多少数对：

给你一个下标从 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 个数字。
1
2
3
4
5
6
7
8
9
10
11

样例 2：

输入：
	nums = [1,1]
	
输出：
	[1,0]
	
解释：
	nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [] 。
	无法形成更多数对。总共形成 1 个数对，nums 中剩下 0 个数字。
1
2
3
4
5
6
7
8
9

样例 3：

输入：
	nums = [0]
	
输出：
	[0,1]
	
解释：
	无法形成数对，nums 中剩下 1 个数字。
1
2
3
4
5
6
7
8

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

---

分析

• 面对这道算法题目，二当家的陷入了沉思。
• 根据题意尽可能多的找出数对，所以最终留下的数字一定出现了奇数次。
• 可以用2次遍历，第一次对数字的出现次数计数，第二次用2整除计数，奇数次的就是会留下的数字。
• 事实上也可以仅遍历一次，一边计数，一边形成数对。

---

题解

rust

impl Solution {
    pub fn number_of_pairs(nums: Vec<i32>) -> Vec<i32> {
        let mut flag = vec![false; 101];
        let mut pairsCount = 0;

        nums.iter().for_each(|&n| {
            let n = n as usize;
            if flag[n] {
                // 多成了一对
                pairsCount += 1;
                flag[n] = false;
            } else {
                // 不成对的数字多了一个
                flag[n] = true;
            }
        });

        return vec![pairsCount, nums.len() as i32 - pairsCount * 2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

go

func numberOfPairs(nums []int) []int {
    flag := make([]bool, 101)
	pairsCount := 0

	for _, n := range nums {
		if flag[n] {
			// 多成了一对
			pairsCount++
			flag[n] = false
		} else {
			// 不成对的数字多了一个
			flag[n] = true
		}
	}

	return []int{pairsCount, len(nums) - pairsCount*2}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

c++

class Solution {
public:
    vector<int> numberOfPairs(vector<int>& nums) {
        bool flag[101] = {};
        int pairsCount = 0;

        for (auto n: nums) {
            if (flag[n]) {
                // 多成了一对
                pairsCount++;
                flag[n] = false;
            } else {
                // 不成对的数字多了一个
                flag[n] = true;
            }
        }

        return {pairsCount, (int) nums.size() - pairsCount * 2};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

java

class Solution {
    public int[] numberOfPairs(int[] nums) {
        boolean[] flag = new boolean[101];
        int pairsCount = 0;

        for (int n : nums) {
            if (flag[n]) {
                // 多成了一对
                pairsCount++;
                flag[n] = false;
            } else {
                // 不成对的数字多了一个
                flag[n] = true;
            }
        }

        return new int[]{pairsCount, nums.length - pairsCount * 2};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

python

class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        flag = [False] * 101
        pairsCount = 0
        for n in nums:
            if flag[n]:
                # 多成了一对
                pairsCount += 1
                flag[n] = False
            else:
                # 不成对的数字多了一个
                flag[n] = True
        return [pairsCount, len(nums) - pairsCount * 2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

原题传送门：https://leetcode.cn/problems/maximum-number-of-pairs-in-array/

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---