java - 数组中最大的可整除子集

Question

给定一个数组，任务是找到数组中最大的可整除子集。如果对于子集中的每一对 (x, y)，要么 x 除 y 要么 y 除 x，则子集称为可整除的。

例子

输入:arr[] = {1, 16, 7, 8, 4} 输出:16 8 4 1 在输出子集中，对于每一对， 第一个元素除以第二个 或先分。

输入:arr[] = {2, 4, 3, 8} 输出:8 4 2

这是我想出的。时间复杂度为 O(n^2)。可以改进吗？

public static int[] largestDivisibleSubset2(int[] a){

    Arrays.sort(a);
    int index=0;
    int maxDivCount=0;
    for(int i=0;i<a.length;i++){
        int currentDivCount=0;
        for (int j=i;j<a.length;j++ ) {
            if(a[j]%a[i]==0){
                currentDivCount++;
            }
        }
        if(currentDivCount>maxDivCount){
            index = i;
            maxDivCount = currentDivCount;
        }
        currentDivCount = 0;
    }
    int[] res = new int[maxDivCount];
    int k=0;
    for(int i=0;i<a.length;i++){
        if(a[i]%a[index]==0){
            res[k++] = a[i];            
        }
    }

    return res;
}

Answer 1

在现代多核机器上(以及在 Java 8 中使用它们的大大改进的设施)，在优化顺序处理时间之前寻找使用所有内核的方法通常更容易。如果降低时间复杂度也会降低可读性或可维护性，则尤其如此。

例如，下面是您的问题的解决方案，它在决定是否向子集添加值时使用 Java 8 中的并行流。在我自己的旧机器上，它可以在 14 秒内找到 50,000 个随机整数的最大可整除子集(如果我删除 parallel 方法，则为 22 秒)。显然可以进行优化，但除非有特定原因，否则请首先选择清晰度。尤其是在采访中:-)

public int[] getSubSet(int... set) {
    int[] largest = new int[0];
    for (int value : set) {
        int[] subset = Arrays.stream(set).parallel()
                .filter(n -> n % value == 0 || value % n == 0).toArray();
        if (subset.length > largest.length)
            largest = subset;
    }
    return largest;
}