一道笔试题（创新工厂）

可以先分别遍历一次两数组，把两个数组先分组，类似桶式排序的方式。

 

然后按分组比较，减少比较次数

最简单的方法，创建一个新数组c，长度为a,b之和。
将长度为N的数组，假设为b，全部填充到c中，
然后将长度为m的数组a的元素，逐个填充到b中，
填充时判断当前值是否已经存在，若存在，说明属于a b 交集元素，
将此元素放入长度为m的数组d中。

最复杂度：M+N次。即没有交集。

另外：个人觉得 排序、List、Set方式，本身已经增加了复杂度。

注：此方法没有考虑数组的顺序性。

每次二分查找后,把查找的结果的index,返回给下一次查找,作为下次数组查找的起始位置,这样每次查找的范围都会变小

def common_element(a,b)
  ce = []
  last_mid = 0
  a,b = b,a if a.size > b.size
  a.each do |i|
    mid = binary_search(i,b,last_mid)
    if i == b[mid]
      ce << i
      last_mid = mid
    end
    p last_mid
  end
end

def binary_search(i,b,last_mid)
  s1 = last_mid
  s2 = (b.size) -1
  mid = (s1+s2)/2
  while(s1 < s2 && b[mid] != i)
    s1 = mid+1 if b[mid] < i
    s2 = mid-1 if b[mid] > i
    mid = (s1+s2)/2
  end
  mid
end

m = [-1,4,5]
n = [-15,1,3,4,5,7,8,9,10,15]
result = common_element(m,n)
p result.join('  ')

结果




这种方法的效率应该没有二分高吧?m+n比较mlogn.
m+n/mlogn化简后(1+n/m)/logn.约等于n/mlogn.因为n>m*m所以n/mlogn>m/logn>m/2logm.明显m/2logm,在m>2的情况下都是大于1的.

感觉题目不是很明确，没说是否重复，和是否是递增型的

给出的例子来说，二分应该不错，最好在每次查找完再截去比它小的元素

你这个的意思不是遍历么?而且不考虑顺序,复杂度也不是M+N.而是M*N.

数字会不会很多？
将数组a插入a表
将数组b插入b表
select * from a
intersect
select * from b
哈哈，会不会复杂度很高？ 

复杂度高不高我不知道 ，只知道工作量比较大

public static void main(String[] args)
    {
        int[] b = { -1, 4, 5 };
       
        int[] a = { -15, 1, 3, 4, 5, 7, 8, 9, 10, 15, 300 };
       
        int aindex = 0;
       
        int bindex = 0;
       
        while (aindex < a.length && bindex < b.length)
        {
            if (a[aindex] == b[bindex])
            {
                System.out.println(a[aindex]);
               
                aindex++;
                bindex++;
               
                continue;
            }
           
            if (a[aindex] < b[bindex])
            {
                aindex++;
                continue;
            }
           
            if (a[aindex] > b[bindex])
            {
                bindex++;
                continue;
            }
        }
    }

  我也发一个：

public class IntersectionCalc {

	public static void main(String[] args) {
		int[] a = { -1, 4, 5, 5 };
		int[] b = { -15, 1, 3, 4, 5, 5, 7, 8, 9, 10, 15 };

		int i = 0, j = 0;
		Integer preValue = null;
		while (i < a.length && j < b.length) {
			if (a[i] < b[j]) {
				i++;
			} else if (a[i] > b[j]) {
				j++;
			} else {
				if (preValue == null || preValue != a[i]) {
					preValue = a[i];
					System.out.print(a[i] + ", ");
				}
				i++;
				j++;
			}
		}

	}

}

 

  创新工厂就考这么简单的笔试题吗

  我等老抛来发话