NutzCN Logo
分享 对面试题的思考,求交集差集
发布于 2905天前 作者 哎呦哥哥 2547 次浏览 复制 上一个帖子 下一个帖子
标签:

在面试的时候,有一道编程题,最后的解决办法想到了使用交集差集去解决。
自己的解决办法很传统,双层循环,list1的每个值和list2的每个值都去比较一下,这样的时间复杂度太高O(m*n)
面试官也提出了这个问题。

想想还有什么方法能够优化一下,思路是这样的:
定义一个map存放lsit,key为lsit1的各个元素,value为该元素出现的次数
把list2的所有元素也放到map里,如果已经存在则value加1
最后根据map里value的值去判断交集和差集
这样我们只需循环m+n次,时间复杂度为O(m+n)

代码如下:

public class Demo {
  
  public static void main(String[] args) {
    List<String> list1 = new ArrayList<String>();
    list1.add("s");
    list1.add("e");
    list1.add("a");
    list1.add("d");
    list1.add("d");
    list1.add("f");
    list1.add("v");
    list1.add("c");
    list1.add("r");
    list1.add("c");
    
    List<String> list2 = new ArrayList<String>();
    list2.add("s");
    list2.add("c");
    list2.add("a");
    list2.add("v");
    list2.add("k");
    list2.add("p");
    list2.add("v");
    list2.add("c");
    list2.add("r");
    list2.add("c");
    
    // s,e,a,d,d,f,v,c,r,c
    // s,c,a,v,k,p,v,c,r,c
    // 交集:s,a,v,c,r
    // 差集:e,d,f,k,p
    
    List<String> alist = Demo.intersection(list1, list2);
    for (String string : alist) {
      System.out.print(string + " ");
    }
    
    System.out.println();
    List<String> blist = Demo.subtraction(list1, list2);
    for (String string : blist) {
      System.out.print(string + " ");
    }
  }
  
  /**
   * 求两个集合的交集
   * 
   * @param list1
   * @param list2
   */
  public static List<String> intersection(List<String> list1, List<String> list2) {
    List<String> result = new ArrayList<String>();
    Iterator<Map.Entry<String, Integer>> itor = calculationFront(list1, list2);
    
    while (itor.hasNext()) {
      Map.Entry<String, Integer> entry = itor.next();
      Integer tmp = entry.getValue();
      if (tmp > 1) {
        result.add(entry.getKey());
      }
    }
    
    return result;
  }
  
  /**
   * 求两个集合的差集
   * 
   * @param list1
   * @param list2
   * @return
   */
  public static List<String> subtraction(List<String> list1, List<String> list2) {
    List<String> result = new ArrayList<String>();
    Iterator<Map.Entry<String, Integer>> itor = calculationFront(list1, list2);
    
    while (itor.hasNext()) {
      Map.Entry<String, Integer> entry = itor.next();
      Integer tmp = entry.getValue();
      if (tmp == 1) {
        result.add(entry.getKey());
      }
    }
    
    return result;
  }
  
  /**
   * 运算前置
   * 
   * @param list1
   * @param list2
   * @return
   */
  public static Iterator<Map.Entry<String, Integer>> calculationFront(List<String> list1,
                                                                      List<String> list2) {
    Map<String, Integer> map = new HashMap<String, Integer>();
    List<String> maxList = list1;
    List<String> minList = list2;
    if (list2.size() > list1.size()) {
      maxList = list2;
      minList = list1;
    }
    
    for (String str : maxList) {
      map.put(str, 1);
    }
    
    for (String str : minList) {
      Integer num = map.get(str);
      if (null != num) {
        map.put(str, ++num);
        continue;
      }
      map.put(str, 1);
    }
    
    return map.entrySet().iterator();
  }
}

还有更快的方法吗?
nutz.cn 貌似还没有这样的帖子吧
@全体

9 回复

为什么 分享 没在 全部 里面显示。。。。

这个。。。我的效率是不是更差呢?

@Test
    public void t3() {
        List<String> list1 = new ArrayList<String>();
        list1.add("a");
        list1.add("b");
        list1.add("c");
        list1.add("d");
        list1.add("e");
        list1.add("f");
        list1.add("g");

        List<String> list2 = new ArrayList<String>();
        list2.add("e");
        list2.add("f");
        list2.add("g");
        list2.add("h");
        list2.add("i");
        list2.add("z");

        Set<String> result = new HashSet<>();
        Set<String> set1 = new HashSet<>(list1);
        Set<String> set2 = new HashSet<>(list2);

        result.clear();
        result.addAll(set1);
        result.retainAll(set2);
        System.out.println("交集:" + result);

        result.clear();
        result.addAll(set1);
        result.removeAll(set2);
        Set<String> result2 = new HashSet<>();
        result2.addAll(set2);
        result2.removeAll(set1);
        result.addAll(result2);
        System.out.println("差集:" + result);

        result.clear();
        result.addAll(set1);
        result.addAll(set2);
        System.out.println("并集:" + result);

    }

@wendal 给一个高效的呗

我只知道有retainAll方法

List<String> aList = ....;
List<String> bList = ...;

aList.retainAll(bList);

哥们,先快排,然后在用n的复杂度可解觉

来自炫酷的 NutzCN

其实和你上面思路一样,二叉树构建复杂度也是nlogn

来自炫酷的 NutzCN

咱们说的复杂度是nlogn
其实和微软一道面试题差不多,你的样例是26个英文字母,开数组,a[n] 代表n字符出现的次数。这样用n的复杂度可以解决

来自炫酷的 NutzCN

我知道可以用sql语句

添加回复
请先登陆
回到顶部