一道笔试题（创新工厂）

当然还要考虑内存了，如果内存放不下要转到硬盘存那就悲剧了

package threadtest;

import java.util.ArrayList;

public class TestA {
	public static void main(String[] args) {

		int[] m = { -1, 4, 5 };
		int[] n = { -15, 1, 3, 4, 5, 7, 8, 9, 10, 15 };

		new TestA().go(m, n);
	}

	private void go(int[] m, int[] n) {

		ArrayList<Integer> result = new ArrayList<Integer>();

		// N数组遍历的起始index
		int defaultJ = 0;

		// 当M数组中有重复的值，直接跳过
		for (int i = 0; i < m.length; i++) {
			if (m[i + 1] == m[i]) {
				continue;
			}

			for (int j = defaultJ; j < n.length - defaultJ; j++) {
				if (m[i] == n[j]) {
					result.add(m[i]);
					// 当N数组中有重复的值，直接跳过
					while (n[j + 1] == n[j]) {
						j++;
					}
					defaultJ = j;
					break;
				}
			}
		}

		for (int i : result)
			System.out.println(i);

	}
}

你怎么不直接调函数，复杂度还O(1)呢?

这是用了二分法的。

package threadtest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class TestA {
	public static void main(String[] args) {
		//
		// int[] m = { -1, 4, 5 };
		// int[] n = { -15, 1, 3, 4, 5, 7, 8, 9, 10, 15 };

		int rate = 10;
		new TestA().go(initArray(rate), initArray(rate * rate + 1));
	}

	private static int[] initArray(int num) {
		int[] ret = new int[num];
		Random r = new Random();

		for (int i = 0; i < num; i++) {
			ret[i] = r.nextInt(100);
		}
		Arrays.sort(ret);

		StringBuffer output = new StringBuffer();
		output.append(num + ":[");
		for (int i = 0; i < ret.length; i++) {
			output.append(ret[i] + ",");
		}
		output.deleteCharAt(output.length() - 1).append("]");
		System.out.println(output.toString());

		return ret;
	}

	private void go(int[] m, int[] n) {

		ArrayList<Integer> result = new ArrayList<Integer>();

		// N数组遍历的起始index
		int defaultJ = 0;
		int temp = 0;

		for (int i = 0; i < m.length; i++) {
			// 当M数组中有重复的值，直接跳过
			if (i + 1 != m.length && m[i + 1] == m[i]) {
				continue;
			}

			temp = Arrays.binarySearch(n, defaultJ, n.length, m[i]);
			if (temp >= defaultJ) {
				// 当N数组中有重复的值，直接跳过
				while (temp + 1 != n.length && n[temp + 1] == n[temp]) {
					temp++;
				}
				defaultJ = temp;
				result.add(m[i]);
			}
		}

		for (int i : result)
			System.out.println(i);

	}
}

Set<Integer> set=new HashSet<Integer>();
StringBuffer buffer = new StringBuffer();
for(int i:m){
	set.add(i);
}
for(int i:n){
	if (set.contains(i)) {
		buffer.append(i).append(",");
	}
}
System.out.println(buffer.substring(0, buffer.length()-1));

不过很奇怪的就是如果m长度在10万级以下的时候HashSet用m比较快
如果10万以上，HashSet用n就比较快了
原因不明，有人能指点下不？我用JDK6跑的

hashset是无序的，这样就破坏了原题给定的条件了

另外我一直闹不明白，楼主的题目是说非降序整型数组，只是说了非降序，并没有说是有序啊，为什么那么多人认为是有序的呢？还是我理解 非降序整型数组 几个字有问题么？

1,1,3,9,3,1,1 同样是非降序 但是也可以非升序的数列，我的理解不知道对么？

9,3 这不是降序是什么？非降序就是升序或者相等。

哦，明白了，谢咯

public class Test1 {

/**
* @param args
*/
public static void main(String[] args) {

int[] m = { -1, 4, 5 };
int[] n = { -15, 1, 3, 4, 5, 7, 8, 9, 10, 15 };
List<Integer> list = mainMethod(conversion(m), conversion(n));
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}

}

public static List<Integer> mainMethod(List<Integer> m, List<Integer> n) {
// 定义要返回的集合
List<Integer> list = new ArrayList<Integer>();
// 由于n>m*m,并且m、n同为整数,可判断n>m
// 为了提高性能,需将m元素少的集合在外部遍历
int sign = 0;
for (int i = 0; i < m.size(); i++) {
System.out.println("外部循环");
for (int j = 0; j < n.size(); j++) {
System.out.println(" 内部循环");
sign++;
if (n.get(j) == m.get(i)) {
System.out.println(" 匹配次数");
list.add(m.get(i));
// 为了提高性能，将以匹配过的元素从数组中删除，减少下一次匹配的次数
n.remove(j);
break;
}
}
}
System.out.println("总共遍历" + sign + "次！");
return list;
}

// 提供Int数组和Integer集合的转换方法
public static List<Integer> conversion(int[] array) {
System.out.println("conversion");
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < array.length; i++) {
list.add(array[i]);
}
return list;
}
}