Проблема двух сумм с HashSet не работает с дубликатами - PullRequest
Новая
       30

Проблема двух сумм с HashSet не работает с дубликатами

0 голосов
/ 14 июня 2019

Я работаю над заданием, в котором мне нужно найти пары чисел, суммирующих до «х» со средним / наилучшим O (n) или линейной сложностью времени выполнения. Я не могу использовать грубую силу, поскольку это увеличит сложность.

Я использую HashSet и использую метод блюда, проверяю, могу ли я найти (x - array [i]) и печатаю его. Но содержит проверки методов для всего HashSet, где я хочу начать поиск после «i» -ой позиции на каждой итерации. Кроме того, я не могу отсортировать их, поскольку я должен распечатать их в порядке их появления во входном массиве. 

          if (hSet.Contains(x - array[i]))
             {
                 Console.Write("(" + array[i] + "," + (x - array[i]) + ")");
                        hSet.Add(array[i]);

                }
             }

с массивом ввода {1, 6, 3, 2, 5, 5, 7, 8, 4, 8, 2, 5, 9, 9, 1};

Мой результат (1,9) (6,4) (3,7) (2,8) (5,5) (5,5) (7,3) (8,2) (4,6) (8,2) (2,8) (5,5) (9,1) (9,1)

Ожидаемый результат: (1,9), (1,9), (6,4), (3,7), (2,8), (2,8), (5,5), (5 , 5), (5,5), (8,2), (8,2), (9,1), (9,1)

1 Ответ

1 голос
/ 14 июня 2019

Этот код работает как ожидание со сложностью O (n) (в большинстве случаев). Использование Dictionary, а не HashSet.

  • Сначала строим словарь из массива, ключом которого является элемент, значением является количество элементов.

  • После этого переберите элементы, сверьтесь со словарем и произведите вывод. Также уменьшите количество этого элемента в словаре, чтобы избежать ненужного вывода позже.

Вот код: 

using System;
using System.Collections.Generic;

class MainClass {
    public static void Main (string[] args) {
        int[] array = { 1, 6, 3, 2, 5, 5, 7, 8, 4, 8, 2, 5, 9, 9, 1 };
        int x = 10;
        // build dictionary
        Dictionary<int,int> dict = new   Dictionary<int,int>();
        for(int i=0; i< array.Length; i+=1){
            if(dict.ContainsKey(array[i])){
                dict[array[i]] += 1;
            } else {
                dict.Add(array[i], 1);
            }
        }
        // using dictionary
        for(int i=0; i< array.Length; i+=1){
            if(dict.ContainsKey(x - array[i])) {
                int count = dict[x - array[i]];
                if(x - array[i] == array[i]){
                    count -= 1;
                }

                for(int j = 0; j< count; j+=1 ) {
                    Console.Write("(" + array[i] + "," + (x - array[i]) + ")");
                }

                dict[array[i]] -=1;
                if(dict[array[i]] == 0){
                    dict.Remove(array[i]);
                }
            }
        }
        Console.WriteLine();
    }
}
...