Учитывая массив целых чисел, найдите первое целое число, которое является уникальным

Question

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

Мое решение: используйте std::map

поставить целое число (число в качестве ключа, его индекс в качестве значения) к немуодин за другим (O(n^2 lgn)), если есть дубликат, удалите запись с карты (O(lg n)), после помещения всех чисел в карту, выполните итерацию карты и найдите ключ с наименьшим индексом O (n).

O(n^2 lgn), поскольку для карты требуется выполнить сортировку.

Это неэффективно.

другие лучшие решения?

Answer 1

Я считаю, что следующее было бы оптимальным решением, по крайней мере, на основе сложности времени / пространства:

Шаг 1: Сохраните целые числа в хэш-карте, в которой целое число является ключом, а количествоколичества раз, когда оно появляется в качестве значения.Обычно это операция O (n) , и вставка / обновление элементов в хеш-таблице должно быть в среднем постоянным временем.Если обнаружено, что целое число появляется более двух раз, вам действительно не нужно увеличивать счетчик использования (если вы этого не хотите).

Шаг 2. Выполните второй проход над целыми числами.Посмотрите каждый на хэш-карте, и первый с числом появлений один - это тот, который вы искали (т. Е. Первое единственное появившееся целое число).Это также O (n) , что делает весь процесс O (n) .

Некоторые возможные оптимизации для особых случаев:

Оптимизация AМожет быть возможно использовать простой массив вместо хеш-таблицы.Это гарантирует O (1) даже в наихудшем случае для подсчета количества вхождений конкретного целого числа, а также поиска количества его появлений.Кроме того, это повышает производительность в реальном времени, так как алгоритм хеширования не нужно выполнять.Может произойти сбой из-за потенциально более плохого местоположения ссылки (то есть, большая разреженная таблица по сравнению с реализацией хеш-таблицы с разумным коэффициентом загрузки).Однако это может быть сделано для очень особых случаев целочисленного упорядочения и может быть смягчено хеш-функцией хеш-таблицы, создающей псевдослучайные размещения в сегментах на основе входящих целых чисел (т. Е. Плохая локальность ссылок для начала).

Каждыйбайт в массиве будет представлять количество (до 255) для целого числа, представленного индексом этого байта.Это было бы возможно только в том случае, если разница между самым низким целым и самым высоким (то есть количеством элементов в области допустимых целых чисел) была достаточно мала, чтобы этот массив помещался в память.Индексом в массиве конкретного целого числа будет его значение минус наименьшее целое число, присутствующее в наборе данных.

Например, на современном оборудовании с 64-разрядной ОС вполне возможно, что массив 4 ГБ можетбыть выделенным, который может обрабатывать весь домен 32-разрядных целых чисел.Возможны даже большие массивы с достаточным объемом памяти.

Наименьшие и наибольшие целые числа должны быть известны перед обработкой, или потребуется другой линейный проход по данным с использованием алгоритма minmax для выяснения этой информации.

Оптимизация B: Вы можете оптимизировать Оптимизация A дальше, используя максимум 2 бита на целое число (один бит указывает на присутствие, а другой указывает на множественность).Это позволило бы представить четыре целых числа на байт, расширив реализацию массива, чтобы обрабатывать больший домен целых чисел для заданного объема доступной памяти.Здесь можно сыграть больше битовых игр, чтобы дополнительно сжать представление, но они будут поддерживать только особые случаи поступления данных и поэтому не могут быть рекомендованы для все еще в основном общего случая.

Answer 2

Все это без причины. Простое использование 2 for-loops & переменной даст вам простой O(n^2) алгоритм.

Если вы берете на себя все хлопоты по использованию хеш-карты, то это может быть то же, что @Micheal Goldshteyn предлагает

ОБНОВЛЕНИЕ: Я знаю, что этому вопросу 1 год. Но просматривал вопросы, на которые я ответил, и наткнулся на это. Мысль, что есть лучшее решение, чем использование хеш-таблицы.

Когда мы говорим «уникальный», у нас будет образец. Например: [5, 5, 66, 66, 7, 1, 1, 77]. В этом случае давайте передвинем окно 3. Сначала рассмотрим (5,5,66). мы можем легко установить. что здесь есть дубликат. Итак, переместите окно на 1 элемент, чтобы мы получили (5,66,66). Тоже самое. перейти к следующему (66,66,7). Снова дупс здесь. следующий (66,7,1). Здесь нет дупов! возьмите средний элемент, так как он должен быть первым уникальным в наборе. Левый элемент принадлежит dup, так же может и 1. Следовательно, 7 - первый уникальный элемент.

пробел: O (1) время: O (n) * O (m ^ 2) = O (n) * 9 ≈ O (n)

Answer 3

@ user3612419

  Solution given you is good with some what close to O(N*N2) but further optimization in same code is possible I just added two-3 lines that you missed.



public static string firstUnique(int[] input)  
{
  int size = input.Length;
  bool[] dupIndex = new bool[size];
  for (int i = 0; i < size; ++i) 
  {
     if (dupIndex[i]) 
    {
        continue;
    } 
    else if (i == size - 1) 
    {
        return input[i].ToString();
    }
    for (int j = i + 1; j < size; ++j) 
    {
  if(dupIndex[j]==true)
  {
 continue;
 }
        if (input[i]==input[j]) 
        {
            dupIndex[j] = true;
    dupIndex[i] = true;
            break;
        } 
        else if (j == size - 1)
        {
            return input[i].ToString();
         }
     } 
  }
return "No unique element";
 }

Answer 4

public static string firstUnique(int[] input)  
{
    int size = input.Length;
    bool[] dupIndex = new bool[size];
    for (int i = 0; i < size; ++i) 
    {
        if (dupIndex[i]) 
        {
            continue;
        } 
        else if (i == size - 1) 
        {
            return input[i].ToString();
        }
        for (int j = i + 1; j < size; ++j) 
        {
            if (input[i]==input[j]) 
            {
                dupIndex[j] = true;
                break;
            } 
            else if (j == size - 1)
            {
                return input[i].ToString();
            }
        }
    }
    return "No unique element";
}

Answer 5

Хотя это O (n ^ 2), следующее имеет малые коэффициенты, не так уж плохо в кеше и использует memmem(), что быстро.

 for(int x=0;x<len-1;x++)
     if(memmem(&array[x+1], sizeof(int)*(len-(x+1)), array[x], sizeof(int))==NULL &&
        memmem(&array[x+1], sizeof(int)*(x-1), array[x], sizeof(int))==NULL)
            return array[x];

Answer 6

Вставка на карту - O(log n), а не O(n log n), поэтому вставка ключей n будет n log n также лучше использовать set.