[JAVA]两个数组取相同元素，能有单层循环的实现么？

0 0

[JAVA]两个数组取相同元素，能有单层循环的实现么？5

m个元素和n个元素的两个数组（具体没要求，假定没排序，有重复），取其中的相同元素

最近看到个面试题，答案说可以用m+n次循环实现，求算法，最好用java实现。
问题补充：
大部分java库函数实现都用了循环，包括List.contains，Map.containsKey，Map.get等等
排序性能也不高，还是没看到什么好的做法，:(

m+n的说法是我书上看到的，看来这年头书也不可靠了
问题补充：
=============================

To RyanPoy:
谢谢回复先

排序性能怎样，我暂时没测试。

想问下，map的实现没有循环么？Map.Entry.next这样做迭代不是循环么
还有，好多地方提到这题的哈希实现的时候都会说是用空间换时间，但是java里具体怎么实现所谓空间换时间的？

附HashMap的containsKey和get都用到的：
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
问题补充：
===============================
自己测试了一下

首先，hash查找确实快，但是对于这题的情况来说，把array put到hash中要花很长时间，普遍情况下，最快的实现还是楼下RyanPoy的先sort在search，再次感谢。

附：
m=n=1000时
Put array to hashtable use 4,508,120ns
Search with Hashtable use 2,861,880ns, found 1
Search with Sort use 6,227,000ns, found 1

m=n=100000时
Put array to hashtable use 108,423,560ns
Search with Hashtable use 30,892,680ns, found 4
Search with Sort use 59,157,680ns, found 4

数组是random生成的

数据结构

2009年7月22日 23:49

wingok
25
0 0 0

5个答案按时间排序按投票排序

0 0

采纳的答案

Arrays.sort(array_1);
Arrays.sort(array_2);
int len = array_1.length
for (int i = 0; i < len; i++)
{
    if (Arrays.binarySearch(array_2, array_1[i]) != -1)
         print array_1[i];
}

1) 排序
2）遍历任意数组（如果是短的效果最好，我这里没有做判断）
3）把一个数组的元素在另外一个数组中2分查找，找到表示交集。

2009年7月23日 12:07

RyanPoy
155
0 0 0

添加评论

0 0

引用

想问下，map的实现没有循环么？Map.Entry.next这样做迭代不是循环么

Map对key的迭代是循环，相当于遍历所有的key。
但是Map对key的定位却不是循环，而是hash

引用

还有，好多地方提到这题的哈希实现的时候都会说是用空间换时间，但是java里具体怎么实现所谓空间换时间的？

这个问题，我想你自己看jdk源代码会更加清楚！

2009年7月27日 09:29

RyanPoy
155
0 0 0

添加评论

0 0

引用

大部分java库函数实现都用了循环，包括List.contains，Map.containsKey，Map.get等等
排序性能也不高，还是没看到什么好的做法，:(

list确实有遍历。
map确没有了。map是采用了hash的方式。你说他们的性能不高？可有什么具体的测试？

2009年7月24日 09:46

RyanPoy
155
0 0 0

添加评论

0 0

import java.util.ArrayList;
import java.util.List;


public class ListTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<String> list1 = new ArrayList<String>(); 
		List<String> list2 = new ArrayList<String>(); 
		list1.add("1"); 
		list1.add("2"); 
		list1.add("3"); 
		list1.add("4"); 
		list1.add("5"); 
		list1.add("6"); 
		list1.add("7"); 
		list1.add("8"); 
		list1.add("9"); 
		list1.add("10"); 

		list2.add("1"); 
		list2.add("3"); 
		list2.add("8"); 

		
		System.out.println(sameList(list1, list2));
		
	}
	
	
	public static List<String> sameList(List<String> list1, List<String> list2)
	{
		List<String> list = new ArrayList<String>();
		String temp;
		for(int i=0; i < list1.size();i++)
		{
			temp = list1.get(i);
			if(list2.contains(temp)){   
				list.add(temp);   
	        }
		}
		
		return list;

	}
	
}

2009年7月23日 08:19