如何改进我的算法？可分度问题

Question

嘿，伙计们，我会解释下面的问题。

键=整数列表我必须找到键中元素的最大可分性程度。但是当我计算可分性的程度时，我应该只考虑键元素。例如：

 keys = [2,4,8,2]
 2 = [2,2] degree of divisibility is 2
 4 = [2,4,2] degree of divisibility is 3
 8 = [2,4,8,2] degree of divisibility is 4 so we choose 8 with 4 degrees of divisibility.

在那之后，我们必须计算

 if maxDegreeOfDivisibility(4 in our case) * 10^5 < validityPeriod* instructionCount then its 
 true. 

我们返回1和4*10^5，我希望我能解释这个问题，如果你们对这个问题有任何疑问的话:D我可以回答。

public static List<Integer> encryptionValidity(int instructionCount, int validityPeriod, 
List<Integer> keys) {
List<Integer> result = Arrays.asList(0, 0);
Map<Integer, Integer> degreeOfDivisibilityCache = new HashMap<>();

for (int i: keys) {
    Integer degreeOfDivisibility = degreeOfDivisibilityCache.getOrDefault(i, -1);

    if (degreeOfDivisibility == -1) {
        int count = 0;
        for (int j : keys) {
            if (j > 0 && i % j == 0) {
                count++;
            }
        }
        degreeOfDivisibilityCache.put(i, count);
    }
}

int maxDegreeOfDivisibility = degreeOfDivisibilityCache.values().stream()
        .max(Comparator.comparingInt(Integer::intValue)).orElse(0);
int s = maxDegreeOfDivisibility * 10000;
result.set(1, s);

BigInteger ic = BigInteger.valueOf(instructionCount);
BigInteger a = ic.multiply(BigInteger.valueOf(validityPeriod));
if (a.compareTo(BigInteger.valueOf(s)) > 0) {
    result.set(0, 1);
}
return result;
}

Answer 1

1. 声明32个桶，每个桶表示一个整数的最重要位
2. 扫描键，记录其出现次数，并将唯一实例放入各自的桶(未排序)，并标记为候选
3. 扫描桶，按它代表的最重要位的降序排列。仅与较低位的桶的内容进行比较。
   • 3.1在可除匹配中，在步骤2中汇总当前计数和出现计数&清除该数字的候选标志
   • 3.2如果当前计数>当前记录保持，设置记录保持器=此键和当前计数

例子: 19，4，12，6，4，3，8

• 发生情况：{19: 1，4: 2，12: 1，6: 1，3: 1，8: 1}
• 桶#16: 19*
• 桶#8: 12*，8*
• 桶#4: 4*，6*
• 桶#2: 3*

1. 扫描19 => 1(自我)；设置记录：(19，1)
2. 扫描12 => 1(自)+2(从4) +1(从6) +1(从3) = 5；清除4，6，3；设定记录：(12，5)
3. 扫描8 => 2
4. 跳过4、6、3

时间复杂度:如果n是整数总数，m是唯一整数数，则在BigO表示法中O(n) + O(m^2)，但实际上O(n) + C*(m^2)/3 (对于某些常数C)

分析：

步骤1中的第一次扫描: O(n)

桶扫描:最坏的情况(满桶)是倒二叉树。这是一个无限系列，总计为1/3 (参见维基百科相关文章：这里和这里)

感谢里克·詹姆斯的候选人旗主意。

Answer 2

1. 排序数字，最大的第一。标出每一个人都是候选人。
2. 对于仍然是候选人的每一个数字： 2.1。数一数在它分成之后的数字。将每一个这样的号码标记为不再是候选人。
3. 在列表中搜索步骤2.1中的最大计数。这个计数是原始列表的可分性程度。

示例：

1. 2,4,8,2,3,6
2. 8*、6*、4*、3*、2*、2*- '*‘意思是“是候选人”

• 检查8: 8*,6*,4,3*,2,2 --可除以4 (8,4,2,2)
• 检查6: 8*,6*,4,3,2,2 --可除以4 (6,3,2,2)
• 其余的不需要检查

1. 答案是4。