Найти числа в списке<int> с заданной разницей

Для заданного списка чисел, разделенных пробелами, каков наиболее эффективный способ подсчета общих пар чисел, которые имеют разность N.

например, командная строка в путе будет:

5 2

где 5 - количество чисел, которым нужно следовать, а 2 - требуемая разница

1 5 3 4 2

5 чисел, которые следует учитывать

Выход должен быть 3, потому что (5,3), (4,2) и (3,1) имеют разность 2

Я могу заставить этот алгоритм работать, но есть ли более эффективный способ сделать это, если у вас есть большие наборы чисел для работы? Я включил три варианта сравнения, и второй должен быть лучше третьего, но есть ли что-то, что я забыл, что могло бы сделать это намного быстрее?

private static void Difference()
{
    string[] firstInput = SplitInput(Console.ReadLine());

    int numberOfNumbers = int.Parse(firstInput[0]);
    int diffOfNumbers = int.Parse(firstInput[1]);

    string[] secondInput = SplitInput(Console.ReadLine());

    List<int> numbers = secondInput.Select(x => Int32.Parse(x)).ToList();

    int possibleCombinations = 0;

    // Option 1
    foreach (int firstNumber in numbers)
    {
        List<int> compareTo = numbers.GetRange(numbers.IndexOf(firstNumber) + 1, numbers.Count - numbers.IndexOf(firstNumber) - 1);

        foreach (int secondNumber in compareTo)
        {
            int diff = firstNumber - secondNumber;

            if (Math.Abs(diff) == diffOfNumbers)
            {
                possibleCombinations++;
            }
        }
    }

    // Option 2
    foreach (int firstNumber in numbers)
    {
        if (numbers.Contains(firstNumber + diffOfNumbers))
        {
                possibleCombinations++;
        }
    }

    // Option 3
    foreach (int firstNumber in numbers)
    {
        foreach (int secondNumber in numbers)
        {
            int diff = firstNumber - secondNumber;

            if(Math.Abs(diff) == diffOfNumbers)
            {
                possibleOptions++;
            }
        }
    }

    Console.WriteLine(string.Format("Possible number of options are: {0}", possibleCombinations));
    Console.ReadLine();
}

private static string[] SplitInput(string input)
{
    return input.Split(new char[1] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
}
Источник

4 ответа

Решение

Если дубликаты номеров не разрешены или их игнорируют (учитываются только уникальные пары), вы можете использовать HashSet<int>:

HashSet<int> myHashSet = ...
int difference = ...
int count;
foreach (int number in myHashSet)
{
    int counterpart = number - difference;
    if (myHashSet.Contains(counterpart))
    {
        count++;
    }
}
Источник

Учитывая ограничения задачи, где N - это "число следующих чисел" [1..N], а M - разница (N=5 и M=2 в примере), почему бы просто не вернуть N - M?

Источник

Это легко сделать с помощью LINQ, допуская дубликаты:

var dict = numbers.GroupBy(n => n).ToDictionary(g => g.Key, g => g.Count());
return dict.Keys.Where(n => dict.ContainsKey(difference-n)).Select(n => dict[difference - n]).Sum();

В первой строке мы создаем словарь, в котором ключами являются различные цифры в списке ввода (numbers) и значения, сколько раз они появляются.

Во-вторых, для каждого отдельного числа в списке (эквивалентного ключам диктовки) мы смотрим, содержит ли словарь ключ для целевого числа. Если это так, мы добавляем количество раз, когда появилось целевое число, которое мы ранее сохраняли в качестве значения для этого ключа. Если нет, мы добавляем 0. Наконец, мы суммируем все.

Обратите внимание, что теоретически это может вызвать арифметическое переполнение, если для элементов в списке нет границ, кроме Int.MinValue и Int.MaxValue. Чтобы обойти это, нам нужно выполнить "безопасную" проверку, которая сначала проверяет, что разница не выйдет за пределы, прежде чем мы попытаемся ее вычислить. Это может выглядеть так:

int SafeGetCount(int difference, int number, Dictionary<int,int> dict)
{
    if(difference < 0 && number < 0 && int.MinValue - difference > number)
        return 0;
    if(difference > 0 && number > 0 && int.MaxValue - difference < number)
        return 0;
    return dict.ContainsKey(difference-number) ? dict[difference - number] : 0;
}

Обновить

Есть несколько вещей, которые, по вашему мнению, совершенно ясны из вашего вопроса, например, хотите ли вы действительно посчитать повторяющиеся пары несколько раз, и поменяется ли число мест на две разные пары. Например, если (1,4) является парой, является (4,1)? Мой ответ выше предполагает, что ответ на оба эти вопроса - да.

Если вы не хотите пересчитывать повторяющиеся пары несколько раз, тогда переходите к HashSet Решение из других ответов. Если вы хотите посчитать дублирующиеся пары, но не хотите пересчитывать дважды, меняя значения в паре, вам придется немного сложнее. Например:

var dict = numbers.GroupBy(n => n).ToDictionary(g => g.Key, g => g.Count());
var sum = dict.Keys.Where(n => n*2 != difference)
      .Where(n => dict.ContainsKey(difference-n))
      .Select(n => dict[difference - n]).Sum()/2;
if(n%2 == 0)
{
    sum += dict.ContainsKey(n/2) ? dict[n/2] : 0
}    
return sum;
Источник

Как насчет сортировки списка, а затем итерации по нему.

int PairsWithMatchingDifferenceCount(
        IEnumerable<int> source,
        int difference)
{
    var ordered = source.OrderBy(i => i).ToList();
    var count = ordered.Count;
    var result = 0;
    for (var i = 0; i < count - 1; i++)
    {
        for (var j = i + 1; j < count; j++)
        {
            var d = Math.Abs(ordered[j] - ordered[i]);
            if (d == difference)
            {
                result++;
            }
            else if (d > difference)
            {
                break;
            }
        } 
    }

    return result;
}

Итак, согласно примеру, вы бы назвали это так,

PairsWithMatchingDifferenceCount(Enumerable.Range(1, 5), 2);

но, если генерация последовательности проста, так как вопрос подсказывает, почему не просто.

var m = 5;
var n = 2;

var result = Enumerable.Range(n + 1, m - n)
                 .Select(x => Tuple.Create(x, x - n)).Count();

или действительно

var result = m - n;
Источник
Другие вопросы по тегам