Careercup - Microsoft面试题 - 24308662
2024-10-20 17:26:40
2014-05-12 07:31
原题:
I have heard this question many times in microsoft interviews. Given two arrays find the intersection of those two arrays. Besides using hash table can we attain the same time complexity that is O(m+n) by using some other approach.
题目:给定两个数组,计算出他们的交集。要求线性时间完成。
解法1:出题者问能否在不用哈希的条件下,用线性时间完成。数组本身不一定是有序的,所以我没想出不用哈希的线性算法。一种可行的解法,是先排序两个数组,然后进行归并,取其交集。显然这种算法的复杂度主要来自排序。
代码:
// http://www.careercup.com/question?id=24308662
// nobody said the elements in both arrays are unique, why would bitset work?
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std; class Solution {
public:
void mergeIntersection(vector<int> &a1, vector<int> &a2, vector<int> &intersect) {
sort(a1.begin(), a1.end());
sort(a2.begin(), a2.end()); int i, j;
int n1, n2; i = ;
j = ;
n1 = (int)a1.size();
n2 = (int)a2.size();
intersect.clear();
while (i < n1 && j < n2) {
if (a1[i] < a2[j]) {
++i;
} else if (a1[i] > a2[j]) {
++j;
} else {
intersect.push_back(a1[i]);
++i;
++j;
}
}
};
}; int main()
{
int n1, n2, n;
vector<int> a1, a2;
vector<int> intersect;
int i;
Solution sol; while (cin >> n1 >> n2 && (n1 > && n2 > )) {
a1.resize(n1);
a2.resize(n2);
for (i = ; i < n1; ++i) {
cin >> a1[i];
}
for (i = ; i < n2; ++i) {
cin >> a2[i];
}
sol.mergeIntersection(a1, a2, intersect); cout << '{';
n = (int)intersect.size();
for (i = ; i < n; ++i) {
i ? (cout << ' '), : ;
cout << intersect[i];
}
cout << '}' << endl;
} return ;
}
解法2:用哈希来搞定,可以在线性时间内完成。统计两个数组中每个值出现的次数,取较少的次数作为交集。比如A[]中有3个“1”,B[]中有5个“1”,那么交集就有3个“1”。
代码:
// http://www.careercup.com/question?id=24308662
// nobody said the elements in both arrays are unique, why would bitset work?
#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std; class Solution {
public:
void mergeIntersection(vector<int> &a1, vector<int> &a2, vector<int> &intersect) {
if (a1.size() > a2.size()) {
mergeIntersection(a2, a1, intersect);
return;
}
unordered_map<int, pair<int, int> > um;
int n1, n2;
int i; n1 = (int)a1.size();
n2 = (int)a2.size();
unordered_map<int, pair<int, int> >::iterator it; for (i = ; i < n1; ++i) {
it = um.find(a1[i]);
if (it == um.end()) {
um[a1[i]] = make_pair(, );
} else {
++it->second.first;
}
} for (i = ; i < n2; ++i) {
it = um.find(a2[i]);
if (it != um.end()) {
++it->second.second;
}
} intersect.clear();
for (it = um.begin(); it != um.end(); ++it) {
n1 = min(it->second.first, it->second.second);
for (i = ; i < n1; ++i) {
intersect.push_back(it->first);
}
} um.clear();
};
}; int main()
{
int n1, n2, n;
vector<int> a1, a2;
vector<int> intersect;
int i;
Solution sol; while (cin >> n1 >> n2 && (n1 > && n2 > )) {
a1.resize(n1);
a2.resize(n2);
for (i = ; i < n1; ++i) {
cin >> a1[i];
}
for (i = ; i < n2; ++i) {
cin >> a2[i];
}
sol.mergeIntersection(a1, a2, intersect); cout << '{';
n = (int)intersect.size();
for (i = ; i < n; ++i) {
i ? (cout << ' '), : ;
cout << intersect[i];
}
cout << '}' << endl;
} return ;
}
最新文章
- jQuery和AngularJS的区别小分析
- Dynamic CRM 2013学习笔记(三十四)自定义审批流5 - 自动邮件通知
- apache-common pool的使用
- android 内存溢出问题分析
- MTD NANDFLASH驱动相关知识介绍
- C++引用计数
- 问题-[Delphi7]程序在WIN7电脑上的日期错误处理
- activity的生命周期详解
- paip.svn使用最佳实践
- pymongo的操作
- [Swift]LeetCode1005. K 次取反后最大化的数组和 | Maximize Sum Of Array After K Negations
- 关于mysql分组查询
- Java将ip字符串转换成整数的代码
- python 在WINDOS虚拟环境部署
- python网站开发准备ubuntu14.04安装mysql实现windows管理
- python之流程控制与运算符
- Swift5 语言指南(十八) 可选链接
- ADO.net之综合演练
- 欧几里得算法(及扩展)&;&;快速幂(二分+位运算)
- 10分钟10行代码开发APP(delphi 应用案例)