优化此C#算法(K差异)

Question

这是我正在解决的问题(这是一个示例问题,而不是真正的问题):

给定N个数,[N <= 10 ^ 5]我们需要计算具有K差异的总数对.[K> 0和K <1e9]

输入格式:第一行包含N&K(整数).第二行包含N个集合.确保所有N个数字都是不同的.输出格式:一个整数表示具有diff K的数字对的no.

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 profiler说要避免调用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);
      }
   }
}

Answer 1

你的算法仍然是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)来确定交集.