虽然看到这个问题会很奇怪,但在我继续我的编码之旅的同时,我真的需要理解一些核心概念。我有一个问题,在Hackerrank上,它像DIVISIBLE SUM PAIRS
我将无论如何给予问题陈述在这里:
问题陈述
给定一个数组,我们需要找到能被给定的数k整除的对的个数,还有一个条件:*arr[i]〈arr[j]
示例
例如,ar=[1,2,3,4,5,6]
和k=5
。我们的三个符合条件的对是[1,4] [2,3]
和[4,6]
。
代码
在我发布代码之前,我想告诉大家,我的代码已经通过了所有的测试用例,可以进入下一个挑战,但是代码中有一个小故障,我正在努力解决。
static int divisibleSumPairs(int n, int k, int[] ar) {
int count = 0;
for(int i=0; i<ar.length; i++){
for(int j=i+1; j<ar.length; j++){
if(((ar[i]+ar[j])%k)==0){
if(i < j)
count++;
}
}
}
return count;
}
这里当我做这个if(i < j) count++
时,它给出了正确的结果,但是当我做这个if(ar[i] < a[j]) count++
时,它应该给了我一个错误的答案。
有人能帮我把这个清除掉吗,比如剩下的是什么?因为我知道检查arr[i] < arr[j]
应该会给予正确的结果。我不想继续错误的知识。
编辑
因为我已经明白我做错了什么。我在代码中有一个修改,就是不以1开始内部循环,因为每次内部循环结束时,它都会以1开始,然后再次运行。我感谢所有帮助我澄清这一点的人,让我的概念足够强大,足以处理这样的问题。
我个人非常感谢Mike 'Pomax' Kamermans、Ricola和xerx593,感谢他们消除了我的疑虑,给了我循环元素的核心概念,这对我以后的工作很有帮助,我不会再重复了。:)
8条答案
按热度按时间oxcyiej71#
我刚刚检查了你的链接,问题语句中给出的条件是
找出并打印(i,j)对的个数,其中i〈j且ar[i] + ar[j]可被k整除。
简单地说就是unordered pairs个元素的个数,这些元素的和可以被k整除。
不管你怎么写
还有一个条件,就是:从这些对中得到arr[i]〈arr[j]。
看起来你误解了这个问题,它解释了为什么
i<j
条件有效,而arr[i] < arr[j]
条件无效。既然你知道你只需要无序对,就不需要从
1
到ar.length
迭代j
。因为你需要j > i
,所以1
和i
之间的每个j
都是无用的。你可以简化你的代码:lyr7nygr2#
当你做
i = {0 ... 10}
和j = {1 ... 10}
时,就会有(大约)100个(i和j的)组合,(大约)50个,其中i〈j,其余的反之亦然。所以你的假设是错误的:应该是给了我一个错误的答案
...它给你正确的错误答案!...既然当
a[i] + a[j] % k == 0
,那么a[j] + a[i] % k == 0
也!如果不包括
if(i < j)
,则会加倍计算(对..的出现次数)。一种(实施)备选方案是:
...用
i + 1
而不是1
初始化内部循环。编辑:(在问题变得更好之后)
您的假设,即
a[i] > a[j]
与i > j
或j < i
等价(但不是两者都等价),几乎是正确的:除了当a[i] == a[j]
时。vdgimpew3#
这是我在javaScript中的解决方案(通过了所有测试用例):
cidc1ykv4#
此解决方案使用javaScript:
flvlnr445#
Python 3中的解决方案(通过所有测试用例):
itertools.combinations(arr,r)函数返回输入可迭代对象的r个元素长度的子序列。组合是按照字典排序的顺序发出的。因此,如果输入可迭代对象是排序的,那么组合元组将按照排序的顺序产生。
tktrz96b6#
如果有人对O(n)解感兴趣,这里是我的C#解。
l5tcr1uw7#
时间复杂度O(n)
lxkprmvk8#
飞镖解决方案