Какой самый быстрый способ определить, содержит ли массив повторяющееся значение? - PullRequest
Новая
       29

Какой самый быстрый способ определить, содержит ли массив повторяющееся значение?

3 голосов
/ 25 апреля 2020

Массив может иметь только один дубликат или вообще не иметь его.

Мне нужен алгоритм, чтобы пройти несколько модульных тестов и иметь разные версии, которые не проходят разные тесты.

Если вы можете Если бы вы нашли что-то не так с этими двумя решениями или знаете более быстрые, я был бы признателен.

Хеширование:

Это не проходит тесты продолжительности для массива размером UInt16.MaxValue с и без повторяющееся значение.

Passed - пустой массив не содержит повтор
Passed - маленький массив без повторов
Passed - небольшой массив с повторением (Repeated)
Passed - малый массив с repeat ( Repeat)
Passed - Большой массив без повторов (Repeated)
Failed - Большой массив без повторов (Duration)
Passed - Большой массив с повторением (Repeated)
Passed - Большой массив с повторением ( Повторите)
Не удалось - Большой массив с повторением (Длительность)
Не удалось - Объединено 

public bool ContainsRepeat(UInt16[] values, out UInt16 repeat)
        {
            //HASH SET//
            var set = new HashSet<UInt16>();
            repeat = 0;
            foreach (UInt16 value in values)
            {
                if (!set.Add(value))
                {
                    repeat = value;
                    return true;
                }
            }
            return false;
         }

Сортировка и затем двоичный поиск дубликатов:

Это не удается Тест на рацион для того же массива размером UInt16.MaxValue, но только когда нет повторений, но также не удается вернуть правильное значение повторения, когда оно есть, даже если оно работает для меньшего массива.

Passed - пустой массив не содержит повтор
Пропущено - Маленький массив без повторов
Пропущено - Маленький массив с повторением (повтор)
Пропущено - Маленький массив с повторением (повтор)
Пропущено - Большой массив без повторов ( Repeated)
Failed - Большой массив без повторов (Duration)
Passed - Большой массив с повторением (Repeated)
Failed - Большой массив с повторением (Repeat)
Passed - Большой массив с повторением (Duration )
Failed - Combined 

public bool ContainsRepeat(UInt16[] values, out UInt16 repeat)
        {
            int findRepeatingElement(UInt16[] arr, int low, int high)
            {
                if (low > high)
                    return -1;

                int mid = (low + high) / 2;

                if (arr[mid] != mid + 1)
                {
                    if (mid > 0 && arr[mid] == arr[mid - 1])
                        return mid;

                    return findRepeatingElement(arr, low, mid - 1);
                }

                return findRepeatingElement(arr, mid + 1, high);
            }

            repeat = 0;
            if (values.Length <= 1)
            {
                return false;
            }

            Array.Sort(values);

            int index = findRepeatingElement(values, 0, values.Length - 1);

            if (index != -1)
            {
                repeat = values[index];
                return true;
            }
            else
            {
                return false;
            }


        }

Это мой первый пост, поэтому приветствуются любые материалы о форматировании будущих вопросов:)

1 Ответ

5 голосов
/ 25 апреля 2020

Создать новый массив bool из элементов UInt16.MaxValue. Используйте этот массив (вместо HashSet) в качестве зонда, чтобы отметить видимое значение и обнаружить последующий дубликат. 

public bool ContainsRepeat(UInt16[] values, out UInt16 repeat)
{
  var seen = new bool[UInt16.MaxValue]; // O(k) space/time; fixed with very small C
  foreach (UInt16 value in values)      // O(n) time; n <= k, with small C
  {
    if (seen[value]) {
      repeat = value;
      return true;
    }
    seen[value] = true;
  }
  repeat = 0;
  return false;
}

Это имеет характеристики O (n + k) времени и O (k) пространства ( k = диапазон), фиксированный. В этом случае k = 2 ^ 16 ~ 65k и n <= k в качестве первого дубликата завершает поиск. </p>

В то время как обе реализации пробного кода имеют O (n), это должно выполнить много лучше, чем использование HashSet из-за меньшей константы (C). Однако такой подход не рекомендуется использовать для набора данных со значениями диапазона UInt32 (например, k = диапазон, где k >> n), так как он оплачивает постоянную инициализацию и стоимость памяти.

Эта характеристика c аналогичен сортировке по радиксу и соответствующим компромиссам между пространством и временем для общей сортировки.

Возможно также применение микрооптимизаций (убедитесь, что эталон в реальных условиях). Очистка существующего массива против создания нового массива; или используя int и increment + check против логического check + set; или используя unsafe, чтобы избежать защиты диапазона индекса.

Если это не удастся в случае «большого» массива ... удачи в «быстром».

...