最近很多人谈论的算法面试题
最近很多人谈论的算法面试题
原文地址：http://blog.sina.com.cn/fulaoshi
有A，B两个数组，B数组中的元素A中都有，现需要生成数组C，将A中有B中没有的元素都放到C里面，要求高效，不能使用工具类。
需求很简单，用一个双重循环也可以做出来，但是说到高效就让人头疼了。其实我一直对于面试考算法持怀疑态度：1，很多算法了解就可以，用的时候网上查，不需要都记在脑子里；2，面试时候难免紧张，要在有限的时间中想出最有效的解决方案，确实强人所难；3，考完算法，你真的要用吗？
特别是关于“高效”这个话题，怎么理解这个效率呢？时间？空间？复杂度？标准并不统一。
废话完毕，抛砖引玉说说这个题，可以定义一个Map集合，将A数组中的每一个元素作为集合的Key，再遍历B数据，将对应的Key删除，剩下的就是C了，代码如下：
A a[] = {1,6,3,65,7,8,31,4,71};
B b[] = {3,1,8,31};
Map map = new HashMap();
for (int i=0; i <a.length; i++) {
map.put(a[i], " ");
}
for (int i=0; i <b.length; i++) {
map.remove(b[i]);
}
C c[] = new int[a.length - b.length];
for (Object o : map.keySet()) {
c[i] = (Integer)o;
}
代码也算简单，思路也算容易理解吧。
效率方面：m+n（m为A的长度，n为B的长度）等级（忽略hashMap中对key进行hash的时间），但是如果A数组元素很多，会浪费一些内容
工具类：不知道map算不算工具类
限制：A，B数组不能有重复的元素，否则要修改算法
希望能看到更好的答案
[匿名] 网友
java.util.* 当然是工具类 util
[匿名] Underwind
……晕，那就自己实现hashMap吧
我觉得util包中，Collections, Arrays算工具类（Helper）
其他的呢……比较暧昧了
[解决办法]
我来谈谈我的想法：
1.对于这个算法设计，最直接的想法就是双重循环，即从A中取出一个元素在B中查询，如果B中没有这个元素，则将这个元素加入到数组C中。这个算法的时间复杂度为O(M*N),其中M和N分别是数组A和B的长度。
2.如果我们将B数组的元素进行排序，则在B中使用二分查找法查找某个元素的时间复杂度就缩减到O(lg(N)),则总的时间复杂度是O(M*lg(N))。
3.我们还应该注意到一个条件，我们需要在A中寻找不在B中出现的元素。则如果A中某个元素在B中出现了，在以后的查询中我们就没有必要在考虑这个元素了。这样B数组中需要查询的元素会随着循环的进行越来越少.可以考虑一个极端的情况:A中前N个元素正好是B的所有元素，这样的时候B中需要查询的元素就为0，那么A中剩下的(M-N)个元素就可以完全放到C中。
有了这样的分析，我们就可以考虑将B中的元素拷贝到一个数据结构中，要求它的查询/删除都应该比较快。
PS:对于面试的算法题，我觉得你的思考的方式比结果更重要。
[解决办法]
时间上考虑，先排序，再求Ａ－Ｂ。。
如果不排序O(m*n)
排序后为m+n + O(sort(A)) + O(sort(B))..
O(sort(A)) 为A排序的时间复杂度。
[解决办法]
一般来说，建立hash表，我们可以将关键字对一个素数求余数，从而在即使关键字取值范围很大时，还是不需要太大的内存。
比如对于B中每个元素，将它们关于19求余数，那么我们就只需要一个大小为19的hash表，冲突的可能性也不大。
[解决办法]
没考虑到高效呢，我现在不考虑效率，想法是这样
1.首先将B中重复元素去掉
2.复制A到C
2.从B中取出一个元素，到C中寻找是否有该元素
3.如果有，从C中删除
4.一直到最后，得到的就是C了
改进还没有什么想法
也就是是否可以使用一些辅助的数据结构或者能否分而治之之类的算法思想了
排序似乎感觉意义不大
[解决办法]
最高效的方法
1. A递增排序, B递增排序
2.
i = 0;
j = 0;
k = 0;
getnext:
if ((A[i] < B[j]) 或 (j超过B的最大下标))
{
C[k] = A[i];
i++;
k++;
}
else if (A[i] = B[j])
{
i++;
j++;
}
else
j++;
if (i 未超过 A的最大下标)
goto getnext;
[解决办法]
假设A、B数组的元素个数分别为m,n(m> n);
1、对B数组建堆，时间复杂性为o(nlg(n)),注意到B本来是个数组，所以额外空间为o(1);
2、将A数组的每个元素在堆上进行比较，由于堆的高度为lg(n),所以这一运算的总时间复杂度为mlg(n)
3、总的复杂性为o(nlg(n)+mlg(n))=o(mlg(n));
4、如果对A进行排序，这一工作的时间复杂性已经达到了o(mlg(m)),不可取。
[解决办法]
public class aa {
public static void main(String[] args) {
int a[] = { 1, 6, 3, 65, 7, 8, 31, 4, 71 };
int b[] = { 1, 3, 8,31 };
int[] c = new int[a.length - b.length];
// 找出a中最大元素,最小元素
int max = 0;
for (int i : a) {
if (i > max) {
max = i;
}
}
// 建立查询表
int temp[] = new int[max + 1];
for (int i : a) {
temp[i] = i;
}
// 将temp中b存在的元素置0
for (int j : b) {
if (temp[j] == j) {
temp[j] = 0;
}
}
// 输出结果
int k=0;
for (int e : a) {
if (temp[e] != 0) {
c[k] = temp[e];
System.out.println(c[k++]);
}
}
}
}
[解决办法]
sheep_sword():
如果a中含有0的话，就不对了吧？
下面：
public static void improvedCorrectWay(){
//计算a的最大值
int max=a[0];
for(int i=1;i <a.length;i++){
if(a[i]> max)
max=a[i];
}
boolean []temp = new boolean[max+1];
for(int i=0;i <a.length;i++){
temp[a[i]]=true;
}
for(int i=0;i <b.length;i++){
temp[b[i]]=false;
}
int []diff = new int[a.length-b.length];
int k=0;
for(int i=0;i <a.length;i++){
if(temp[a[i]])
diff[k++]=a[i];
}
Arrays2.print(diff);
}
时间复杂度为：O(M),M为a的长度。
空间复杂度就糟糕了。
[解决办法]
10个桶 根据a数组中基数放入桶中每个桶记录数目n
然后b数组放入记录数目m
n = m 桶中直接删除 m = 0输出删除
n != m 其它类似
