java 可除和对

h43kikqp  于 2022-11-27  发布在  Java
关注(0)|答案(8)|浏览(111)

虽然看到这个问题会很奇怪,但在我继续我的编码之旅的同时,我真的需要理解一些核心概念。我有一个问题,在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' KamermansRicolaxerx593,感谢他们消除了我的疑虑,给了我循环元素的核心概念,这对我以后的工作很有帮助,我不会再重复了。:)

oxcyiej7

oxcyiej71#

我刚刚检查了你的链接,问题语句中给出的条件是
找出并打印(i,j)对的个数,其中i〈j且ar[i] + ar[j]可被k整除。
简单地说就是unordered pairs个元素的个数,这些元素的和可以被k整除。
不管你怎么写
还有一个条件,就是:从这些对中得到arr[i]〈arr[j]
看起来你误解了这个问题,它解释了为什么i<j条件有效,而arr[i] < arr[j]条件无效。
既然你知道你只需要无序对,就不需要从1ar.length迭代j。因为你需要j > i,所以1i之间的每个j都是无用的。你可以简化你的代码:

static int divisibleSumPairs(int n, int k, int[] ar) {
    int count = 0;
    for(int i=0; i<ar.length-1; i++){
      for(int j=i+1; j<ar.length; j++){
            if(((ar[i]+ar[j])%k)==0){
                   count++;
            }
        }
    }
    return count;
}
lyr7nygr

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),则会加倍计算(对..的出现次数)。
一种(实施)备选方案是:

for (int i = 0; i < ar.length; i++) {
  // ensure i < j via initialization ;)
  for (int j = i + 1; j < ar.length; j++) {
    if (((ar[i]+ar[j]) % k) == 0) {
      counter++;
    }
  }
}

...用i + 1而不是1初始化内部循环。
编辑:(在问题变得更好之后)
您的假设,即a[i] > a[j]i > jj < i等价(但不是两者都等价),几乎是正确的:除了当a[i] == a[j]时。

vdgimpew

vdgimpew3#

这是我在javaScript中的解决方案(通过了所有测试用例):

function divisibleSumPairs(n, k, ar) {
    let count=0;
    
    for(let i=0; i<n; i++){
        for(let j=0; j<n; j++){
            if(i<j){
              if((ar[i]+ar[j])%k===0) count++; 
            }
        }
    }
    return count;
}
cidc1ykv

cidc1ykv4#

此解决方案使用javaScript:

divisibleSumPairs (n, k, ar) => {
  let count = 0;
  ar = ar.map((value, index, arr) => {
    for (let i = index + 1; i <= arr.length; i++) {
      if ((value + arr[i]) % k === 0) {
        count++;
      }
    }
  });
  return count
}
flvlnr44

flvlnr445#

Python 3中的解决方案(通过所有测试用例):
itertools.combinations(arr,r)函数返回输入可迭代对象的r个元素长度的子序列。组合是按照字典排序的顺序发出的。因此,如果输入可迭代对象是排序的,那么组合元组将按照排序的顺序产生。

from itertools import combinations

def divisibleSumPairs(n,ar,k):
    pairs = []
    for com in combinations(ar,2): 
        if sum(com) % k == 0:
            pairs.append(com)
    return len(pairs)

nk = input().split()
n = int(nk[0])
k = int(nk[1])            
ar = list(map(int, input().rstrip().split()))
print(divisibleSumPairs(n,ar,k))
tktrz96b

tktrz96b6#

如果有人对O(n)解感兴趣,这里是我的C#解。

public static int divisibleSumPairs(int n, int k, List<int> ar)
{
    Dictionary<int, int> map = new Dictionary<int, int>();
    int cnt = 0;
    
    foreach (int elem in ar)
    {
        int modulo = elem % k;
        int complement = modulo == 0 ? 0 : k - modulo;
        
        if (map.ContainsKey(complement))
        {
            cnt += map[complement];
        }
        
        if (map.ContainsKey(modulo))
        {
            ++map[modulo];
        }
        else
        {
            map.Add(modulo, 1);
        }
    }
    
    return cnt;
}
l5tcr1uw

l5tcr1uw7#

def divisibleSumPairs(n, k, ar):
    result = 0
    d = {}

    for i in range(n):
        mod = ar[i] % k
        result += d.get(( k - mod ) % k, 0)
        d[mod] = d.get(mod, 0) + 1

    return result

时间复杂度O(n)

lxkprmvk

lxkprmvk8#

飞镖解决方案

n = arr.length;
int numberOfDivisiblePairs = 0;
for (int i = 0; i < n; i++) {
  for (int j = i + 1; j < n; j++) {
    if (arr[i] + arr[j] % k == 0) {
      numberOfDivisiblePairs++;
    }
  }
}
return numberOfDivisiblePairs;

相关问题