Optimization of this C # algorithm (K Difference)

Question

This is the problem I am solving (this is a trial problem, not a real problem):

Given N numbers, [N <= 10 ^ 5], we must calculate the complete pairs of numbers that have a difference K. [K> 0 and K <1e9]

Input format: 1st line contains N and K (integers). The second line contains N numbers of the set. All N rooms are guaranteed to be excellent. Output format: single integer indicating the absence of pairs of numbers that have a diff 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 

I already have a solution (and I could not optimize it, as I hoped). My solution is currently getting a 12/15 score when it is running, and I wonder why I cannot get 15/15 (my solution to another problem was not so effective, but got all the points). Apparently, the code runs using "Mono 2.10.1, C # 4".

So can anyone think of a better way to optimize this further? The VS profiler says to avoid calling String.Split and Int32.Parse. It is impossible to avoid Int32.Parse calls, although I think I could optimize the array tokenization.

My current solution:

 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

Your algorithm is still O (n ^ 2), even when sorting and starting. And even if you deleted the O (n ^ 2) bit, the sorting is still O (n lg n). You can use O (n) algorithm to solve this problem. Here is one way to do this:

Suppose you have set the value S1 = { 1, 7, 4, 6, 3 } , and the difference is 2.

Build the set S2 = { 1 + 2, 7 + 2, 4 + 2, 6 + 2, 3 + 2 } = { 3, 9, 6, 8, 5 } .

The answer you are looking for is the intersection power of S1 and S2. The intersection {6, 3} , which has two elements, so the answer is 2.

You can implement this solution in one line of code, provided that you have a sequence of integers sequence and integer difference :

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

The Intersect method will build an effective hash table for you, which is O (n) to determine the intersection.

Answer 2

Try this (note, not verified):

• Array Sort
• Start two indexes at 0
• If the difference between the numbers in these two positions is K, increase the number and increase one of the two indices (if the numbers are not duplicated, increase both)
• If the difference is greater than K, increase the index C # 1
• If the difference is less than K, increase the index C # 2, if this takes it outside the array, you will end
• Otherwise, return to 3 and continue driving.

Basically, try dividing the two indexes by the difference in K.

You should write a series of unit tests for your algorithm and try to come up with edge cases.

Answer 3

This will allow you to do this in one go. Using hash sets is useful if there are many values ​​for analysis or verification. You can also use a color filter in combination with hash sets to reduce your search.

• Initialize. . Let A and B be two empty hash sets. Let c be zero.
• Analysis cycle. Parsing the next value of v. If there are no more values, the algorithm is executed, and the result is in c.
• Check back. If v exists in A, then increment c and return to 2.
• Low match. If v - K> 0, then:
  • insert v - K into A
  • if v - K exists in B, then the increment c (and, optionally, removes v - K from B).
• High compliance. If v + K <1e9, then:
  • insert v + K into A
  • if v + K exists in B, then the increment c (and, optionally, removes v + K from B).
• Remember. Insert v into B.
• Go back to 2.

Answer 4

// php solution for this k-difference

 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"); 

Answer 5

Actually, what is trivial to solve with hashmap:

First, put each number in the hash map: dict((x, x) for x in numbers) in the pythony pseudocode;)

Now you just iterate over each number in the hash map and check if the number + K is in the hash map. If so, increase the quantity by one.

The obvious improvement of the naive solution is ONLY checking for a higher (or lower) border, otherwise you will get double results and should divide by 2 after - it's useless.

This is O (N) to create a hashmap when reading in and O (N) values ​​when iterating through, i.e. O (N) and around 8loc in python (and rightly so, I just solved it ;-))

Answer 6

After Eric’s answer, insert the implementation of the Interscet method below, this is 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; }