有人说用归并算法，但是执行下来时间远远不止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++];
}
}
}
大家讲道理2017-04-18 10:53:41
アイデアを提供するために、探しているのは 2 つの配列で同じ電話番号です。次に、最初の配列の電話番号から 辞書ツリー を構築します。
2 回目以降は、辞書ツリーで直接検索するだけです。全体的な複雑さは O(N * 11) = O(N) です。電話番号ごとに 11 桁。合計の複雑さはわずか O(N) です。
参照Zhihu: https://zhuanlan.zhihu.com/p/...
巴扎黑2017-04-18 10:53:41
メソッドを見つけたところ、実行時間は約2秒です:
リーリーこのメソッドの主なアイデアは、最初に並べ替えてから、Arrays.binarySearch() メソッドを使用してバイナリ クエリを実行し、一致する配列添字を返すことです。
データソースの取得方法を変更したところ、ランダムデータソースを使用した場合、エラー時間は主にsort()ソートメソッドで消費されることがわかりました。ソートアルゴリズムの時間計算量。
コードは次のように変更されます:
パブリッククラス TestB {
リーリー}
迷茫2017-04-18 10:53:41
考察ビットマップ、参考https://github.com/RoaringBit... } }
RoaringBitmap aBM = new RoaringBitmap()
for (int i = 0; i
...
RoaringBitmap interactionBM = RoaringBitmap.and(aBM, bBM)
for (int item: interactionBM) {
大家讲道理2017-04-18 10:53:41
この操作が配列内でのみ実行できる場合、トリックはなく、少なくとも小さい配列を走査する必要があり、さらにはソートが避けられません。また、配列の内容を他のデータ構造にエクスポートできる場合、質問の本来の意図に違反しているようです。質問者は配列操作をテストしたかったのでしょうか?
ringa_lee2017-04-18 10:53:41
もっと簡単な方法を考えてみましょう。MBP では約 200 ミリ秒しかかかりません。通常のPentium G2020では250msしかかかりません
うーん、このアルゴリズムは全く不可能です。
高洛峰2017-04-18 10:53:41
実際、アルゴリズムがこの質問の鍵です。
『Programming Pearls』の最初の章を読むことをお勧めします。良いアイデアを提供してくれるでしょう。
まず第一に、質問を洗練する必要があります。つまり、携帯電話番号は中国の携帯電話番号のみである必要がありますか?そうでなければ、その数はさらに大きくなるでしょう。
Zhuji で電話番号がどのように保存されるかを簡単に説明しましょう。
すべての携帯電話番号を保存するために 2 進数のみを使用します。 2 進数は非常に長くなる場合があります。長さは、可能な最大の電話番号と同じです。たとえば、13999999999 は、実際には 999999999 桁の 2 進数です。
各桁に、この電話番号がある場合は 1 とマークされ、ない場合は 0 とマークされます。
簡単にするために、携帯電話番号の範囲は 0 ～ 9 であると仮定します。まず、10 桁の 2 進数 0000000000 を準備します。
最初の配列には 3 つの電話番号、つまり 1、5、7 があると仮定します。このとき、この配列を格納する 2 進数は 0010100010 です。この 1、5、7 ビットは数値は 1 で、他のビットは 0 です。
2 番目の配列に 6 つの電話番号、つまり 1、2、3、4、7、8 があるとします。この配列を格納する 2 進数は 0110011110 で、この配列の 1、2、3、4、7、8 桁です。上位ビットは 1、他のビットは 0 です。
それでは、これら 2 つの配列で同じ電話番号を見つけるにはどうすればよいでしょうか?
ビット演算では「ビットごとの AND」(AND) 演算を行うだけで済みます。同じビットが両方とも 1 の場合は 1 のままです。どちらか 1 つが 0 である限り、それは 0 です。
0010100010 & 0110011110 = 0010000010
1桁目と7桁目が1の2進数であることがすぐに分かりました。
