算法问题，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

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

}

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
额，这种算法完全不行，?，其实是错误的，修正后也很费时间。。。囧，果然还是嫩了啊

        int len_a = 50000000;
        int len_b = 10000000;

        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 before = System.currentTimeMillis();
        Arrays.sort(a);
        Arrays.sort(b);

        int index_a = 0;
        int index_b = 0;

        List<Long> list = new ArrayList<>();
        while (index_a != (len_a - 1) && index_b != (len_b - 1)) {
            if (a[index_a] > b[index_b]) {
                index_b++;
            } else if (a[index_a] < b[index_b]) {
                index_a++;
            } else {
                list.add(a[index_a]);
                index_a++;
                index_b++;
            }
        }

        long after = System.currentTimeMillis();
        System.out.println("used: " + (after - before));

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的一个二进制数。