给一个m*n的二维整型数组,各行之间可能有重复出现的数字,要求输出所有在每 一行都出现的数(可能有多个)
时间: 2024-03-15 21:44:24 浏览: 54
可以使用哈希表来解决这个问题。具体步骤如下:
1. 定义一个哈希表 unordered_map<int, int> freq,并初始化为 0。
2. 遍历二维数组,对于数组中的每个元素 nums[i][j],将其作为键,在哈希表中对应的计数器加 1。
3. 遍历哈希表 freq,对于其中的每个键值对 (k, v),如果 v 等于数组的行数 m,则说明 k 在每一行都出现过,将其加入到结果集合中。
4. 返回结果集合。
以下是使用 C++ 实现的代码示例:
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
vector<int> findCommonNums(vector<vector<int>>& nums) {
int m = nums.size(), n = nums[0].size();
unordered_map<int, int> freq;
// 遍历二维数组,统计每个数字出现的次数
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
freq[nums[i][j]]++;
}
}
vector<int> res;
// 遍历哈希表,找到在每一行都出现的数字
for (auto& [k, v] : freq) {
if (v == m) {
res.push_back(k);
}
}
return res;
}
int main() {
vector<vector<int>> nums = {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {3, 4, 6}};
vector<int> res = findCommonNums(nums);
for (int num : res) {
cout << num << " ";
}
return 0;
}
```
以上代码使用哈希表来统计每个数字出现的次数,并且使用哈希表的键来存储数字,哈希表的值来存储数字出现的次数。最后,遍历哈希表,找到在每一行都出现的数字,并将其加入到结果集合中。时间复杂度为 O(mn),空间复杂度为 O(mn)。
阅读全文