問題描述

有人說用歸并算法，但是執行下來時間遠遠不止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++];} }}

問題解答

提供一個思路，我們要找的是兩個數組里相同的電話號碼。那么我們把第一個數組的電話號碼建立一顆 字典樹。在第二個的時候直接在 字典樹 里查找即可。總體是一個 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;}@Overridepublic 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(); }}回答2：

剛剛找到一種方法，執行時間大概在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);}

}

考慮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)

}

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

http://tieba.baidu.com/p/3866...

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();回答7：

redis SINTER(返回一個集合的全部成員，該集合是所有給定集合的交集。)

如果說這個操作只能在數組中進行的話，沒什么取巧的辦法，至少要遍歷較小的那個數組，甚至排序都是免不了的。而如果可以將數組內容導出到其他數據結構的話，又貌似有違題目初衷的嫌疑。出題者是不是想考驗數組操作呢？

來一種更簡單的方法，在MBP上只要200ms左右。普通的Pentium G2020也只要250ms額，這種算法完全不行，回答10：

這題目其實算法是關鍵。建議大家看一下編程珠璣的第一章。會提供很好的思路。首先問題必須細化一下，就是手機號必須只有中國的手機號嗎。否則數量會多很多。我簡單說一下編程珠璣里是怎樣存儲電話號碼的。他是只使用一個二進制的數字來存儲所有的手機號碼。一個二進制的數位可以很長很長。長度就等于最大的可能的那個電話號碼。比如說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的一個二進制數。