java - 算法问题，2个数组，数组a保存1000W条手机号，数组b保存5000W条，找出两个数组相同的手机号，执行时间需要 <2s

Question

有人说用归并算法，但是执行下来时间远远不止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++];
        }
    }

}

Answer 1

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

Answer 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);
}

}

Answer 3

考慮點陣圖，參考https://github.com/RoaringBit...
RoaringBitmap aBM = new RoaringBitmap()
for (int i = 0; i < a.length; i++) {

雷雷

}
...
RoaringBitmapinteractionBM = RoaringBitmap.and(aBM, bBM)
for (int item:interactionBM) {

雷雷

}

Answer 4

        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

Answer 5

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

Answer 6

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();

Answer 7

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

Answer 8

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

Answer 9

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

Answer 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的一個二進制數。