logo标签列表

优化这个C#算法（K差异）

c#optimization
7
这是我要解决的问题（这只是一个样例问题，不是真正的问题）：
给定N个数字，[N≤10^5]，我们需要计算差值为K的总数对。[K>0和K<1e9]
输入格式：第一行包含N和K（整数）。第二行包含集合中的N个数字。所有N个数字都保证是不同的。
输出格式：一个整数，表示具有差异K的数字对的数量。
Sample Input #00:
5 2
1 5 3 4 2
Sample Output #00:
3
Sample Input #01:
10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Sample Output #01:
0

我已经有一个解决方案了（但我还没有能够像我希望的那样进行优化）。目前，我的解决方案在运行时得分为12/15，我想知道为什么我不能获得15/15的分数（我的另一个问题的解决方案不太高效，但却获得了所有的分数）。显然，代码是使用“Mono 2.10.1，C# 4”运行的。

那么，有人能想到更好的方法来进一步优化吗？ VS分析器建议避免调用String.Split和Int32.Parse。虽然无法避免对Int32.Parse的调用，但我想我可以优化数组的标记化。

我的当前解决方案：

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace KDifference
{
   class Solution
   {
      static void Main(string[] args)
      {
         char[] space = { ' ' };

         string[] NK = Console.ReadLine().Split(space);
         int N = Int32.Parse(NK[0]), K = Int32.Parse(NK[1]);

         int[] nums = Console.ReadLine().Split(space, N).Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray();

         int KHits = 0;

         for (int i = nums.Length - 1, j, k; i >= 1; i--)
         {
            for (j = 0; j < i; j++)
            {
               k = nums[i] - nums[j];

               if (k == K)
               {
                  KHits++;
               }
               else if (k < K)
               {
                  break;
               }
            }
         }

         Console.Write(KHits);
      }
   }
}
我们没有注册就看不到那个问题。你能发布一下你们评分的标准吗？ - George Duckett
是的，抱歉。我以为这对所有人都开放。具体的评分标准没有公布，但代码会经过一系列测试运行。 - Neal P
1
你会因为慢或者错误而扣分吗？还是两者都会扣分？ - Lasse V. Karlsen
6个回答
30

即使您进行了排序和提前退出操作，您的算法仍然是O(n^2)。即使您消除了O(n^2)的部分，排序仍然是O(n lg n)的。 您可以使用O(n)的算法来解决此问题。以下是一种方法：

假设您有的集合是S1 = { 1, 7, 4, 6, 3 }，差值为2。

构建集合S2 = { 1 + 2, 7 + 2, 4 + 2, 6 + 2, 3 + 2 } = { 3, 9, 6, 8, 5 }。

您要找到的答案是S1和S2的交集的基数。它们的交集是{6, 3}，其中有两个元素，因此答案是2。

如果您有一个整数序列sequence和一个整数difference，则可以使用一行代码实现此解决方案：

int result = sequence.Intersect(from item in sequence select item + difference).Count();

Intersect方法会为您构建一个高效的哈希表，其时间复杂度为O(n)，用于确定交集。

这个算法真的很令人印象深刻。你能提供一些关于这类算法的资源吗？ - sahid
@Eric Lippert：是否有可能在不使用O(n^2)复杂度的情况下找到两个数组的交集？ - Chetna
@Chetna：我提供了一个时间复杂度为O(n)的序列算法。数组也是一种序列，所以答案是肯定的。 - Eric Lippert
1

// 这是解决k差问题的PHP方案

function getEqualSumSubstring($l,$s) {
$s = str_replace(' ','',$s);
$l = str_replace(' ','',$l);

for($i=0;$i<strlen($s);$i++)
{
   $array1[] = $s[$i];
}
for($i=0;$i<strlen($s);$i++)
{
   $array2[] = $s[$i] + $l[1];
}
return count(array_intersect($array1,$array2));

}

echo getEqualSumSubstring("5 2","1 3 5 4 2");
1
尝试这个（注意，未经测试）：
  1. 对数组进行排序
  2. 从0开始两个索引
  3. 如果这两个位置上的数字之差等于K，则增加计数，并增加其中一个索引（如果数字不是重复的，则同时增加两者）
  4. 如果差大于K，则增加索引#1
  5. 如果差小于K，则增加索引#2。如果那将它放置在数组外面，你就完成了
  6. 否则，请返回3并继续
基本上，尝试通过K值差保持两个索引分开。
你应该为你的算法编写一系列单元测试，并尝试想出边缘情况。
所有的N个数字都保证是不同的。 - CodesInChaos
使用O(n log n)的解决方案，而不是同样简单的O(n)解决方案。 - Voo
1

这将使您可以在一次遍历中完成。如果有许多值需要解析/检查，则使用哈希集很有好处。您还可能想要使用布隆过滤器与哈希集结合使用以减少查找。

  1. 初始化。 让A和B成为两个空的哈希集合。让c为零。
  2. 解析循环。 解析下一个值v。如果没有更多的值，则算法完成，并且结果在c中。
  3. 回溯检查。 如果v存在于A中，则增加c并跳回2。
  4. 低匹配。 如果v-K>0，则：
    • 将v-K插入到A中
    • 如果v-K存在于B中，则增加c（并可选地从B中删除v-K）。
  5. 高匹配。 如果v+K<1e9，则：
    • 将v+K插入到A中
    • 如果v+K存在于B中，则增加c（并可选地从B中删除v+K）。
  6. 记住。 将v插入到B中。
  7. 跳回2。
0

根据Eric的回答，将Interscet方法的实现粘贴在下面，它是O(n)的：

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
    Set<TSource> set = new Set<TSource>(comparer);
    foreach (TSource current in second)
    {
        set.Add(current);
    }
    foreach (TSource current2 in first)
    {
        if (set.Remove(current2))
        {
            yield return current2;
        }
    }
    yield break;
}
0

实际上，使用哈希表解决这个问题非常简单：

首先将每个数字放入哈希表中：dict((x, x) for x in numbers) 在“Python”伪代码中;)

现在，您只需遍历哈希表中的每个数字，并检查是否存在哈希表中的数字+K。如果是，则增加计数。

对于朴素解决方案的明显改进是仅检查较高（或较低）边界，否则会得到双重结果，之后必须除以2-无用。

在读取值时创建哈希表的时间复杂度为O（N），在迭代时为O（N），即O（N），在Python中大约为8行代码（它是正确的，我刚刚解决了它;-)）

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接