有人说用归并算法,但是执行下来时间远远不止2s。
在下实在想不出还有什么好办法,希望各位能给个提示或者解法,谢谢。
下面是我的测试代码:
public class TestA { public static void main(String[] args) { long[] a = new long[50000000]; long num = 13000000000l; for (int i = 0; i < a.length; i++) { a[i] = (num + i); } long[] b = new long[10000000]; long num2 = 14000000000l; for (int i = 0; i < b.length - 2; i++) { b[i] = (num2 + i); } b[9999999] = 13000000000l; b[9999998] = 13000000001l; long[] c = new long[a.length+b.length]; long start = System.currentTimeMillis(); for (int i = 0; i < a.length; i++) { c[i] = a[i]; } for (int i = 0; i < b.length; i++) { c[i + a.length] = b[i]; } System.out.println("start"); sort(c, 0, c.length-1); long end = System.nanoTime(); System.out.println(System.currentTimeMillis() - start); for (int i = 0; i < c.length; i++) { System.out.println(c[i]); } } public static void sort(long[] data, int left, int right) { if (left < right) { // 找出中间索引 int center = (left + right) / 2; // 对左边数组进行递归 sort(data, left, center); // 对右边数组进行递归 sort(data, center + 1, right); // 合并 merge(data, left, center, right); } } public static void merge(long[] data, int left, int center, int right) { long[] tmpArr = new long[data.length]; int mid = center + 1; // third记录中间数组的索引 int third = left; int tmp = left; while (left <= center && mid <= right) { // 从两个数组中取出最小的放入中间数组 if (data[left] <= data[mid]) { if(data[left] == data[mid]){ System.out.println(data[left]); } tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } // 剩余部分依次放入中间数组 while (mid <= right) { tmpArr[third++] = data[mid++]; } while (left <= center) { tmpArr[third++] = data[left++]; } // 将中间数组中的内容复制回原数组 while (tmp <= right) { data[tmp] = tmpArr[tmp++]; } } }
这题目其实算法是关键。
建议大家看一下编程珠玑的第一章。会提供很好的思路。
首先问题必须细化一下,就是手机号必须只有中国的手机号吗。否则数量会多很多。
我简单说一下编程珠玑里是怎样存储电话号码的。
他是只使用一个二进制的数字来存储所有的手机号码。一个二进制的数位可以很长很长。长度就等于最大的可能的那个电话号码。比如说13999999999,其实13可以省掉,我们的这个数字就是999999999位的一个二进制数。
在每一位上,如果有这个电话号码,就标记为1,如果没有就标记为0.
为了简单起见,我就假设手机号的范围是0-9,我们先准备一个10位的二进制数0000000000.
假设第一个数组有3个电话号码,分别是1,5,7,那么存储这个数组的二进制数就是0010100010,这个数字的1,5,7位上是1,其他位是0。
假设第二个数组有6个电话号码,分别是1,2,3,4,7,8那么存储这个数组的二进制数就是0110011110,这个数字的1,2,3,4,7,8位上是1,其他位是0。
那么如何找出这两个数组中相同的电话呢?
只需要做一下位运算中“按位与”(AND)的操作即可,同一位上两个都是1的,还是1,只要有一个是0的,就是0。
0010100010 & 0110011110 = 0010000010
一下就找出来是第1位和第7位上是1的一个二进制数。
来一种更简单的方法,在MBP上只要200ms左右。普通的Pentium G2020也只要250ms
额,这种算法完全不行,
如果说这个操作只能在数组中进行的话,没什么取巧的办法,至少要遍历较小的那个数组,甚至排序都是免不了的。而如果可以将数组内容导出到其他数据结构的话,又貌似有违题目初衷的嫌疑。出题者是不是想考验数组操作呢?
redis SINTER(返回一个集合的全部成员,该集合是所有给定集合的交集。)
C#, 本地运行,release,611ms
long[] a = new long[50000000];
long num = 13000000000L;
for (int i = 0; i < a.Length; i++)
{
a[i] = (num + i);
}
long[] b = new long[10000000];
long num2 = 14000000000L;
for (int i = 0; i < b.Length - 2; i++)
{
b[i] = (num2 + i);
}
b[9999999] = 13000000000L;
b[9999998] = 13000000001L;
var hashSetB = new HashSet<long>(b);
var matches = new List<long>();
var timer = new System.Diagnostics.Stopwatch();
Console.WriteLine("Starts...");
timer.Start();
for (var i = 0; i < a.Length; i++)
{
if (hashSetB.Contains(a[i]))
{
matches.Add(a[i]);
}
}
timer.Stop();
Console.WriteLine(timer.ElapsedMilliseconds);
Console.WriteLine("Found match: " + string.Join(", ", matches));
Console.ReadLine();
http://tieba.baidu.com/p/3866...
long start = System.currentTimeMillis(); HashSet<Long> alongs = new HashSet<>(); for (long l : b) { alongs.add(l); } ArrayList<Long> sames = new ArrayList<>(); for (long l : a) { if (alongs.contains(l)) { sames.add(l); } } long end = System.currentTimeMillis(); System.out.println(end - start);
使用上述代码,在我的机器上,是8s
考虑bitmap, 参考https://github.com/RoaringBit...
RoaringBitmap aBM = new RoaringBitmap()
for (int i = 0; i < a.length; i++) {
aBM.add(a[i])
}
...
RoaringBitmap interactionBM = RoaringBitmap.and(aBM, bBM)
for (int item: interactionBM) {
System.out.println(item)
}
刚刚找到一种方法,执行时间大概在2s左右:
public class TestB { static long count; public static void main(String[] args) { long[] a = new long[50000000]; long num = 13000000000l; for (int i = 0; i < a.length; i++) { a[i] = num + i; } long[] b = new long[10000000]; long num2 = 14000000000l; for (int i = 0; i < b.length - 3; i++) { b[i] = num2 + i; } b[9999999] = 13000000000l; b[9999998] = 13000000002l; b[9999997] = 13000000002l; long start = System.currentTimeMillis(); Arrays.sort(a); int flag = -1; for (int i = 0; i < b.length; i++) { count = b[i]; flag = Arrays.binarySearch(a, count); if (flag <= 50000000 && flag >= 0) { System.out.println(count + " " +flag); } } System.out.println(System.currentTimeMillis() - start); } }
这个方法主要思想是先排序,再使用 Arrays.binarySearch()方法进行二分法查询,返回匹配的数组下标。
修改了一下获取数据源的方法,发现如果使用随机数据源,耗费的时间是8s左右,误差时间主要消耗在sort()排序方法上,数据源的规律还是影响排序算法的时间复杂度的。
代码修改如下:
public class TestB {
static long count; public static void main(String[] args) { System.out.println(random()); long[] a = new long[50000000]; for (int i = 0; i < a.length; i++) { a[i] = random(); } long[] b = new long[10000000]; for (int i = 0; i < b.length; i++) { b[i] = random(); } long start = System.currentTimeMillis(); Arrays.sort(b); Arrays.sort(a); int flag = -1; int cc =0; for (int i = 0; i < b.length; i++) { count = b[i]; flag = Arrays.binarySearch(a, count); if (flag <= 50000000 && flag >= 0) { System.out.println(count + " " + flag); cc++; } } System.out.println("相同数据的数量:"+cc); System.out.println(System.currentTimeMillis() - start); } public static long random() { return Math.round((new Random()).nextDouble()*10000000000L+10000000000L); }
}
提供一个思路,我们要找的是两个数组里相同的电话号码。那么我们把第一个数组的电话号码建立一颗 字典树。
在第二个的时候直接在 字典树 里查找即可。总体是一个 O(N * 11) = O(N) 的复杂度。每个电话号码 11 位的话。总的只是一个 O(N) 的复杂度。
参考知乎:https://zhuanlan.zhihu.com/p/...
public class TrieTree { private class Node { char ch; TreeMap<Character, Node> node; int count; public Node(char ch) { ch = this.ch; node = new TreeMap<>(); count = 0; } } public class StringCount implements Comparable{ public String str; public int count; public StringCount(String str, int count) { this.str = str; this.count = count; } @Override public int compareTo(Object o) { StringCount t = (StringCount) o; if(this.count > t.count){ return -1; } if(this.count < t.count){ return 1; } return 0; } } private int indexStringCount; private StringCount[] stringCounts; private Node root; private int size; private static boolean DEBUG = true; public TrieTree() { root = new Node('$'); size = 0; } public int insert(String str) { int res = 0; Node temp = root; for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); if (temp.node.get(ch) == null) temp.node.put(ch, new Node(ch)); temp = temp.node.get(ch); } if(temp.count == 0) size ++; res = ++temp.count; return res; } public StringCount[] getStringCount(){ indexStringCount = 0; stringCounts = new StringCount[this.size]; ergodic(root, ""); Arrays.sort(stringCounts); { for(StringCount s : stringCounts){ System.out.println(s.str + " " + s.count); } } return stringCounts; } private void ergodic(Node foo, String str){ if(foo.count != 0){ stringCounts[indexStringCount ++] = new StringCount(str, foo.count); } for(Character ch:foo.node.keySet()){ ergodic(foo.node.get(ch), str + ch); } } private void show(Node foo, String str) { if (foo.count != 0) { System.out.println(str + " : " + foo.count); } for(Character ch:foo.node.keySet()){ show(foo.node.get(ch), str + ch); } } public void showALL() { show(root, ""); } public int size(){ return size; } public static void main(String[] args) { TrieTree tree = new TrieTree(); String[] strs = { "a", "aa", "a", "b", "aab", "bba" }; for (int i = 0; i < strs.length; i++) { tree.insert(strs[i]); } tree.showALL(); System.out.println(tree.size); tree.getStringCount(); } }