問(wèn)題描述

有人說(shuō)用歸并算法，但是執(zhí)行下來(lái)時(shí)間遠(yuǎn)遠(yuǎn)不止2s。在下實(shí)在想不出還有什么好辦法，希望各位能給個(gè)提示或者解法，謝謝。

下面是我的測(cè)試代碼：

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; // 對(duì)左邊數(shù)組進(jìn)行遞歸 sort(data, left, center); // 對(duì)右邊數(shù)組進(jìn)行遞歸 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記錄中間數(shù)組的索引int third = left;int tmp = left;while (left <= center && mid <= right) { // 從兩個(gè)數(shù)組中取出最小的放入中間數(shù)組 if (data[left] <= data[mid]) {if(data[left] == data[mid]){ System.out.println(data[left]);}tmpArr[third++] = data[left++]; } else {tmpArr[third++] = data[mid++]; }}// 剩余部分依次放入中間數(shù)組while (mid <= right) { tmpArr[third++] = data[mid++];}while (left <= center) { tmpArr[third++] = data[left++];}// 將中間數(shù)組中的內(nèi)容復(fù)制回原數(shù)組while (tmp <= right) { data[tmp] = tmpArr[tmp++];} }}

問(wèn)題解答

提供一個(gè)思路，我們要找的是兩個(gè)數(shù)組里相同的電話(huà)號(hào)碼。那么我們把第一個(gè)數(shù)組的電話(huà)號(hào)碼建立一顆 字典樹(shù)。在第二個(gè)的時(shí)候直接在 字典樹(shù) 里查找即可。總體是一個(gè) O(N * 11) = O(N) 的復(fù)雜度。每個(gè)電話(huà)號(hào)碼 11 位的話(huà)。總的只是一個(gè) O(N) 的復(fù)雜度。參考知乎：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：

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

這個(gè)方法主要思想是先排序，再使用 Arrays.binarySearch()方法進(jìn)行二分法查詢(xún)，返回匹配的數(shù)組下標(biāo)。

修改了一下獲取數(shù)據(jù)源的方法，發(fā)現(xiàn)如果使用隨機(jī)數(shù)據(jù)源，耗費(fèi)的時(shí)間是8s左右，誤差時(shí)間主要消耗在sort()排序方法上，數(shù)據(jù)源的規(guī)律還是影響排序算法的時(shí)間復(fù)雜度的。代碼修改如下：

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('相同數(shù)據(jù)的數(shù)量：'+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);

使用上述代碼，在我的機(jī)器上，是8s

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

C#, 本地運(yùn)行，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(返回一個(gè)集合的全部成員，該集合是所有給定集合的交集。)

如果說(shuō)這個(gè)操作只能在數(shù)組中進(jìn)行的話(huà)，沒(méi)什么取巧的辦法，至少要遍歷較小的那個(gè)數(shù)組，甚至排序都是免不了的。而如果可以將數(shù)組內(nèi)容導(dǎo)出到其他數(shù)據(jù)結(jié)構(gòu)的話(huà)，又貌似有違題目初衷的嫌疑。出題者是不是想考驗(yàn)數(shù)組操作呢？

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

這題目其實(shí)算法是關(guān)鍵。建議大家看一下編程珠璣的第一章。會(huì)提供很好的思路。首先問(wèn)題必須細(xì)化一下，就是手機(jī)號(hào)必須只有中國(guó)的手機(jī)號(hào)嗎。否則數(shù)量會(huì)多很多。我簡(jiǎn)單說(shuō)一下編程珠璣里是怎樣存儲(chǔ)電話(huà)號(hào)碼的。他是只使用一個(gè)二進(jìn)制的數(shù)字來(lái)存儲(chǔ)所有的手機(jī)號(hào)碼。一個(gè)二進(jìn)制的數(shù)位可以很長(zhǎng)很長(zhǎng)。長(zhǎng)度就等于最大的可能的那個(gè)電話(huà)號(hào)碼。比如說(shuō)13999999999，其實(shí)13可以省掉，我們的這個(gè)數(shù)字就是999999999位的一個(gè)二進(jìn)制數(shù)。在每一位上，如果有這個(gè)電話(huà)號(hào)碼，就標(biāo)記為1，如果沒(méi)有就標(biāo)記為0.為了簡(jiǎn)單起見(jiàn)，我就假設(shè)手機(jī)號(hào)的范圍是0-9，我們先準(zhǔn)備一個(gè)10位的二進(jìn)制數(shù)0000000000.假設(shè)第一個(gè)數(shù)組有3個(gè)電話(huà)號(hào)碼，分別是1，5，7，那么存儲(chǔ)這個(gè)數(shù)組的二進(jìn)制數(shù)就是0010100010，這個(gè)數(shù)字的1，5，7位上是1，其他位是0。假設(shè)第二個(gè)數(shù)組有6個(gè)電話(huà)號(hào)碼，分別是1，2，3，4，7，8那么存儲(chǔ)這個(gè)數(shù)組的二進(jìn)制數(shù)就是0110011110，這個(gè)數(shù)字的1，2，3，4，7，8位上是1，其他位是0。那么如何找出這兩個(gè)數(shù)組中相同的電話(huà)呢？只需要做一下位運(yùn)算中“按位與”（AND）的操作即可，同一位上兩個(gè)都是1的，還是1，只要有一個(gè)是0的，就是0。0010100010 & 0110011110 = 0010000010

一下就找出來(lái)是第1位和第7位上是1的一個(gè)二進(jìn)制數(shù)。