问一个简单的算法问题

Question

有这么两个字符串数组
String strA = {"h","k","i", "e"}
String strB = {"a","b","c","d","e","f","g","h","i","j","k"}现在我要找出strA和strB的交集并输出，请问要怎么做？
如果按照这种方法效率肯定不高，要怎样改进？for(String str1 : strA)
{
    for(String str2 : strB)
    {
        if(str1.equals(str2))
           ....
    }
}

Answer 1

用集合吧
String[] strA = {"h","k","i", "e"};
String[] strB = {"a","b","c","d","e","f","g","h","i","j","k"};
List<String> l1 = new ArrayList<String>(Arrays.asLit(strA));
List<String> l2 = new ArrayList<String>(Arrays.asLit(strB));
l1.retainAll(l2); //交集 l1.removeAll(l2)差集 l1.addAll(l2)并集
String[] sab = l1.toArray(new String[0]);
for (String s : sab) {
    System.out.println(s);
}

Answer 2

    public boolean retainAll(Collection<?> c) {
boolean modified = false;
Iterator<E> e = iterator();
while (e.hasNext()) {
    if (!c.contains(e.next())) {
e.remove();
modified = true;
    }
}
return modified;
    }我不认为用API的方法会比自己写一个for循环效率高。

Answer 3

API一般都是优化后的解决方案。。

Answer 4

我一般会利用Map键不可以重复的特点来做。        String[] strA = { "h", "k", "i", "e" };
        String[] strB = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k" };        Map<String, Integer> map = new HashMap<String, Integer>();
        for (String str : strA)
        {
            map.put(str, 1);
        }
        System.out.print("并集是：");
        for (String str : strB)
        {
            if (map.containsKey(str))
            {
                System.out.print(str + " ");
            }
        }

Answer 5

这是你自己写的for吗？这是API源代码
    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over this collection, checking each
     * element returned by the iterator in turn to see if it's contained
     * in the specified collection.  If it's not so contained, it's removed
     * from this collection with the iterator's <tt>remove</tt> method.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> if the iterator returned by the
     * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
     * and this collection contains one or more elements not present in the
     * specified collection.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     *
     * @see #remove(Object)
     * @see #contains(Object)
     */
    public boolean retainAll(Collection<?> c) {
boolean modified = false;
Iterator<E> e = iterator();
while (e.hasNext()) {
    if (!c.contains(e.next())) {
e.remove();
modified = true;
    }
}
return modified;
    }
一般情况下，源代码(也就是API)都是优化过的，自己写的算法未必如API优，当然，某种情况下，API为了照顾全面会牺牲一些性能，而自己写的算法是针对某种具体情况可能会高效一些，但毕竟是少数

Answer 6

这样是提高了效率么？还不如直接for循环呢、、、

Answer 7

这个要看LZ的数据量，两个for嵌套的算法本来就不如API的算法优，因为两个for都是线性查找
5L的相对也好一些，其实和Collecton.contains()等效
当然，如果只是针对LZ这些数据，还可以这样做
int[] cnt = new int[26];
for (int i=0; i<a.length; i++) {
    cnt[strA[i].charAt(0)-'a']++;
}
List<String> list = new ArrayList<String>();
for (int i=0; i<b.length; i++) {
    int j = strB[i].charAt(0)-'a';
    cnt[j]++;
    if (cnt[j] == 2) {list.add(strB[i])}; //直接用数组定位，不用查找
}

Answer 8

我就是从API里找的，其实API里的方法更多的时候是要全面照顾的，所以针对不同的情况，我们要选择不同的方法。比如楼主这个，我认为他写那个for循环就已经可以了。创建一个Iterator的开销还是很大的

Answer 9

呵呵，此人没搞过Web开发鉴定完毕。

Answer 10

我觉得这个方式只是不让我们自己写循环去处理，但是调用的api方法还是用api去处理，而且还多了数组转换到列表的过程，真的不一定比自己写的循环快
就如3楼说的那样
如果追求效率的话，就不一定要追求是用api去处理，可以针对api的方式自己写一个处理出来，会少好多转化的步骤

Answer 11

public class Main {
/**
 * @author Liutao
 */
public static void main(String[] args) {
String[] strA = {"h","k","i", "e"};
String[] strB = {"a","b","c","d","e","f","g","h","6","j","k"};
String strAA = "";
for(String s: strA){
strAA +=s;
}
for(String s: strB){
if(strAA.contains(s)){
System.out.println(s);
}
}
}
}

Answer 12

public class Test {
public static void main(String[] args) {        
        String[] strA = {"h","k","i", "e"};
        String[] strB = {"a","b","c","d","e","f","g","h","i","j","k"};
        List resultStr = new ArrayList();
        List listStrA = Arrays.asList(strA);
        for (int i = 0; i < strB.length; i++) {
         if (listStrA.contains(strB[i])) {
         resultStr.add(strB[i]);
         }
        }
        
        System.out.println("交集：" + resultStr);   }}
交集：[e, h, i, k]