在一个差值为K的数组中找出对的个数

本文关键字：数组 一个 | 更新日期: 2023-09-27 18:13:45

所以我要做的就是

static int NumdiffExponential(int[] arr, int K)
{
    return (from i in arr
            from j in arr
            where (j - i) == K
            select 1).Count();
}

，除非在线性时间内，最好使用单个LINQ查询，并且以紧凑，可读和微优化的方式。所以我想到的是尝试

static int NumdiffLinear(int[] arr, int K)
{
    var counters = 
        arr
        .GroupBy(i => i)
        .ToDictionary(g => g.Key, g => g.Count());
    return 
        counters
        .Keys
        .Aggregate(
            0, 
            (total, i) => total + counters[i] * (counters.ContainsKey(K - i) ? counters[K - i] : 0)
        ); 
}

总是显示为0，我不知道为什么。

让我解释一下我认为它是如何工作的。如果我们有arr={1,1,1,2,3,3,5}和K=2，那么counter就像

1->3, 2->1, 3->2, 5->1

让count = 0 .

我取键1，看到1-K=-1不是counter中的键，因此count =仍然是0。与2键相同。

对于3，我们有3-K=1，它是counter中的一个键。密钥1有3次出现(即counter[3]=1)，密钥2有2次出现。因此count = 3*2 = 6因为双(1,3)(1,3),(1,3),(1,3),(1,3),(1,3),(1、3)可以形成。

通过与上面相同的逻辑，由于对(3,5)，我们向count添加了一个。所以答案是count = 7。

我的算法或它的实现有什么问题?

在一个差值为K的数组中找出对的个数

更具可读性和紧凑性:

static int NumdiffLinear(int[] arr, int K)
{
    return arr.SelectMany(v => arr, (a, b) => new { a, b })
                .Where(s => s.b - s.a == K)
                .Count();
}

这是一个具有相同原理的线性:

static int NumdiffLinear(int[] arr, int K)
{
    int n = 1;
    return arr.Select(value => new { value, index = n++ }) //Get number and index
                .SelectMany(indexValue => arr.Skip(indexValue.index), (a, b) => new { a = a.value, b }) //Project it with the next elements in the array
                .Where(s => s.a - s.b == K) //Do the math
                .Count();
}

Replace 

(total, i) => total + counters[i] * (counters.ContainsKey(K - i) ? counters[K - i] : 0)


(total, i) => total + counters[i] * (counters.ContainsKey(i-K) ? counters[i-K] : 0)

你应该做加法而不是减法。例如你知道你有key = 1和K = 2。然后你必须检查key = (1+2)是否存在。

在你的O(n^2)算法中你检查J - I == K。现在假设您只有I和K。简单的数学运算，只要做J = K + I，如果条件成立，那么J应该存在。

(total, i) => total + counters[i] * (counters.ContainsKey(K + i) ? counters[K + i] : 0)

您可以按如下方式修复您的解决方案，

public int NumdiffLinear(int[] arr, int K)
        {
            var dupsDictionary =
                arr
                    .GroupBy(i => i)
                    .ToDictionary(g => g.Key, g => g.Count());

            return dupsDictionary.Keys.Aggregate(
                0,
                (total, i) =>
                    total +
                    dupsDictionary.Keys.Where(key => i - key == K)
                        .Sum(key => dupsDictionary[key]*dupsDictionary[i]));
        }
相关文章：