公司申请注册流程_注册新公司网上办理流程_市场调研报告模板ppt_排名优化哪家专业

目录

题目链接：2341. 数组能形成多少数对 - 力扣（LeetCode）

题目描述

解法一：List集合

Java写法：

运行时间

C++写法：

 

解法二：Set集合

Java写法：

运行时间

C++写法

上述两种方法的时间复杂度和空间复杂度

空间复杂度

总结

解法三：Map集合（最清晰的写法）

Java写法：

运行时间

C++写法

总结

题目描述

解法一：List 集合

解法二：Set 集合

解法三：Map 集合

总结

---

题目链接：2341. 数组能形成多少数对 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给你一个下标从 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 <= 100
• 0 <= nums[i] <= 100

---

解法一：List集合

• 初始化数据结构：使用一个 List<String> 作为存储结构，set 用于记录当前未配对的元素。count 用于统计配对的数量。

• 遍历数组：通过增强的 for 循环遍历输入数组 nums 中的每个元素。

• 判断配对：

  • 对于每个元素，将其转换为字符串，并检查 set 中是否已存在该字符串。
  • 如果存在，说明找到了一个配对，此时从 set 中移除该元素，并将 count 增加 1。
  • 如果不存在，则将该元素的字符串形式添加到 set 中，表示该元素未配对。

• 返回结果：最后，返回一个整数数组，其中第一个元素是配对的数量 count，第二个元素是 set 的大小，代表未配对的元素数量。

Java写法：

class Solution {public int[] numberOfPairs(int[] nums) {List<String> set = new ArrayList<>();int count = 0;for (int i : nums) {if (set.contains(Integer.toString(i))) {set.remove(Integer.toString(i));count++;} else {set.add(Integer.toString(i));}}return new int[]{count, set.size()};}
}

运行时间

C++写法：

 

#include <vector>
#include <unordered_set>
#include <string>class Solution {
public:std::vector<int> numberOfPairs(std::vector<int>& nums) {std::unordered_set<int> set; // 使用哈希集来存储未配对的元素int count = 0;for (int num : nums) {if (set.find(num) != set.end()) {set.erase(num); // 找到配对，移除该元素count++;} else {set.insert(num); // 未找到配对，添加该元素}}return {count, static_cast<int>(set.size())}; // 返回配对数量和未配对元素数量}
};

 

---

解法二：Set集合

        这个方法和List集合的实现思路一模一样，只是实现方式不同而已，所以我就不再做过多的介绍了。

Java写法：

class Solution {public int[] numberOfPairs(int[] nums) {Set<Integer> set = new HashSet<>();int count = 0;for (int i : nums) {if (set.contains(i)) {set.remove(i);count++;} else {set.add(i);}}return new int[]{count, set.size()};}
}

运行时间

C++写法

#include <vector>
#include <unordered_set>class Solution {
public:std::vector<int> numberOfPairs(std::vector<int>& nums) {std::unordered_set<int> set; // 使用哈希集来存储未配对的元素int count = 0;for (int num : nums) {if (set.find(num) != set.end()) {set.erase(num); // 找到配对，移除该元素count++;} else {set.insert(num); // 未找到配对，添加该元素}}return {count, static_cast<int>(set.size())}; // 返回配对数量和未配对元素数量}
};

 

---

上述两种方法的时间复杂度和空间复杂度

1. 遍历数组：代码中使用一个 for 循环遍历输入数组 nums，这个过程的时间复杂度是 O(n)，其中 n 是数组的长度。

2. 集合操作：

   • set.contains(Integer.toString(i))：在使用 List 的情况下，查找一个元素的时间复杂度是 O(m)，其中 m 是列表的当前大小。最坏情况下，当所有元素都不同时，m 会接近 n，因此查找操作可能达到 O(n)。
   • set.remove(Integer.toString(i)) 和 set.add(Integer.toString(i))：在列表中，移除和添加元素的时间复杂度也是 O(m)。

        综上所述，使用后list方法，由于在每次循环中都涉及到 contains、remove 和 add 操作，每次的操作时间都是 O(n)，因此整体的时间复杂度为 O(n^2)。

空间复杂度

1. 存储结构：使用了一个 List<String> 来存储未配对的元素。在最坏情况下，如果所有元素都不同，set 的大小将达到 n，因此空间复杂度为 O(n)。

总结

• 时间复杂度：O(n^2) — 由于每个元素的查找、添加和移除操作都在列表中进行，导致在最坏情况下时间复杂度为 O(n^2)。
• 空间复杂度：O(n) — 存储未配对的元素，在最坏情况下可能需要存储 n 个不同的元素。

        这种实现虽然思路清晰，但在效率上不够高，特别是对于较大的输入数组。如果使用 HashSet 替代 List，则时间复杂度可以优化为 O(n)，空间复杂度仍为 O(n)。

---

解法三：Map集合（最清晰的写法）

• HashMap：使用 HashMap<Integer, Integer> 来存储每个整数及其出现次数。

• 计数：通过遍历 nums 数组，更新哈希表，使用 getOrDefault 方法来简化计数过程。

• 计算配对数和剩余数：

  • 遍历哈希表中的值，计算配对数（每一对由两个数构成）和剩余数（对 2 取余）。

• 返回结果：返回一个整数数组，数组的第一个元素是配对的数量，第二个元素是剩余的整数数量。

Java写法：

class Solution {public int[] numberOfPairs(int[] nums) {HashMap<Integer, Integer> countMap = new HashMap<>();// 计数每个整数的出现次数for (int num : nums) {countMap.put(num, countMap.getOrDefault(num, 0) + 1);}int pairs = 0;int remaining = 0;// 计算配对数和剩余数for (int count : countMap.values()) {pairs += count / 2;          // 每一对由两个相同的数构成remaining += count % 2;      // 剩余未配对的数}return new int[]{pairs, remaining};}
}

运行时间

C++写法

#include <vector>
#include <unordered_map>class Solution {
public:std::vector<int> numberOfPairs(std::vector<int>& nums) {std::unordered_map<int, int> countMap; // 哈希表存储每个整数及其出现次数// 计数每个整数的出现次数for (int num : nums) {countMap[num]++;}int pairs = 0;int remaining = 0;// 计算配对数和剩余数for (const auto& entry : countMap) {pairs += entry.second / 2;         // 每一对由两个相同的数构成remaining += entry.second % 2;     // 剩余未配对的数}return {pairs, remaining}; // 返回配对数量和剩余整数数量}
};

---

总结

题目描述

• 输入一个下标从 0 开始的整数数组 nums。
• 可以从中选出两个相等的整数，形成一个数对并移除。
• 返回一个长度为 2 的整数数组，其中 answer[0] 是形成的数对数目，answer[1] 是剩下的整数数目。

解法一：List 集合

• 使用 ArrayList 存储未配对的元素，通过字符串形式进行查找。
• 由于查找操作时间复杂度为 O(n)，整体复杂度为 O(n²)。

解法二：Set 集合

• 使用 HashSet 存储未配对的元素，查找、添加和移除操作的平均时间复杂度为 O(1)。
• 时间复杂度优化为 O(n)，空间复杂度为 O(n)。

解法三：Map 集合

• 使用 HashMap 统计每个整数的出现次数。
• 遍历哈希表计算配对数和剩余数。
• 时间复杂度为 O(n)，空间复杂度为 O(n)，是较清晰且高效的解法。

总结

• 不同的数据结构影响算法的效率。
• 使用 HashSet 和 HashMap 比使用 ArrayList 更能提高性能，尤其在大数据量时。