置换优化问题很多,但每个问题都不相同。
在最近的一次编码作业中,有人给了我一串数字,让我找出有多少对数字之和是60的倍数。
我想出了以下解决方案:
public int getPairs(List<Integer> nums){
int result = 0;
for(int i=0; i<nums.size(); i++){
for(int j=i; j<nums.size(); j++) {
if((nums.get(i)+nums.get(j))%60 == 0){
result++
}
}
}
return result;
}
这段代码是正确的,但是测试软件没有通过一些隐藏的测试用例,其中数字列表是10000,因为“超时”,这意味着它花了太长的时间。
我试着先将List转换为数组,以保存size()
和get()
方法调用,但它对我没有帮助。
我很困惑,这不是检查所有可能组合的最快方法吗?
如果问题不是问60的倍数,而是问60,那么我会先对数组进行排序,一旦和大于60,就跳过数组的其余部分,但情况并非如此。
而且,10,000大小的数组会超时也很奇怪。10,000 x 10,000是1000000。当然,在现代处理器上,做两个加法、除法、比较和比较到零10000000应该花不到一秒的时间。
是我做错了什么,还是测试软件有问题?
2条答案
按热度按时间puruo6ea1#
解释错误
这段代码是正确的,但是测试软件没有通过一些隐藏的测试用例,其中数字列表是10000,因为“超时”,这意味着它花了太长的时间。
我不会说代码是正确的(因为它有一个缺陷),相反,您没有机会看到它在一个小的输入失败。
在内部
for
-循环中,我们将索引j
的起始值初始化为i
-int j = i
,这意味着在内部循环的第一次迭代中,我们将向自身添加一个元素***:nums.get(i) + nums.get(j)
,然后检查它是否可被60
整除。这可能会导致无效的结果。内部循环应该以
j = i + 1
开始。有了这个修复,你会得到一个正确的暴力解决方案。第二个问题-术语。
你的代码所计算的是不是**Permutations,而是Combinations的元素对(这不是学术上的争论,结果会有所不同)。
举个简单的例子,假设输入是
[1,2,3]
,我们需要可被3
整除的元素对的组合,这里只有一个组合:[1,2]
,但有两种排列:[1,2]
和[2,1]
。因为在你的暴力解决方案中
i < j
总是成立的,所以它不能生成置换(因为它不在内部循环中重新访问相同的索引,所以它只能考虑[i,j]
,而不能考虑[j,i]
),它生成的是组合的数量。现在,当问题陈述得到澄清时: “求出可被给定数整除的组合对的个数”*,让我们来看看实际的解决方案。
溶液
正如 @Joachim Sauer 在注解中指出的,解决这个问题的第一步是创建一个由数组元素
% 60
组成的频数数组(就像Counting排序算法的第一阶段一样)。那么我们有两种情况:
[1,29]∪[31,59]
中除以60
的余数时,我们需要计算相应余数的频率Cartesian product,并将其加到总数中,即frequency(1)xfrequency(59)
、frequency(2)xfrequency(58)
、...一直到frequency(29)xfrequency(31)
。注意我们不应该接触frequency(0)
和frequency(30)
(它们需要单独处理),我们不应该重复计算乘积,也就是说,我们不应该考虑像frequency(59)xfrequency(1)
这样的反向组合。frequency(0)
和frequency(30)
是一种特殊情况,因为我们只能将它们自身进行合并。对于这两种情况,我们需要根据以下公式计算一个 * 二项式系数 *:其中,
n
是频率数(对于0
或对于30
),k
是组合中的元素数,始终等于2
。这就是实现的样子(* 为了简化测试,除数
60
没有硬编码,而是作为方法参数提供 *):main()
camsedfj2#
获取此代码