Как найти «нечетный» в списке чисел - PullRequest
Новая
       46

Как найти «нечетный» в списке чисел

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

У меня есть массив чисел [x1, x2, x3 и т. Д.], Размер которого превышает 20 элементов, и я пытаюсь составить алгоритм для сортировки элементов по "странности", которую они имеют по отношению костальная часть списка.

Я определяю «странность» как расстояние от барицентров, учитывая некоторый порог T1.Барицентры - это то место, где значения имеют тенденцию концентрироваться, возможно, с учетом некоторого второго порогового значения T2.

Пример: [20, 20, 21, 31, 24, 20, 70, 21, 31,24, 20, 20, 21, 31, 24, 20, 20, 21, 31, 24] и T1 = 10 Барицентр составляет около 24, и только нечетный из них равен 70

Этот случай тривиален, так какзнакомая метрика «расстояние от среднего или среднего» подойдет, например.d (70) = | 24-70 | = 46> 10 = T1 и d (31) = | 24-31 | = 7 <10 = T1 </p>

Я не могу понять, как бороться сболее общий случай наличия двух или более барицентров.

Пример 2: [20, 20, 21, 31, 24, 20, 70, 21, 31, 24, 120, 120, 121, 131, 124, 120, 120, 121, 131, 124] Теперь есть два барицентра d1 = 24 и d2 = 124, и единственный нечетный - все еще 70

Но предыдущая метрика разбивается.Возможно, самая сложная задача - выяснить, какие барицентры.

Примечание: я ищу быстрый алгоритм, а не точный

1 Ответ

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

Похоже, основная проблема, которую вы пытаетесь решить, состоит в следующем: нарисуйте как можно меньше кругов радиус-R, чтобы все входные данные были покрыты хотя бы одним кружком; затем найдите круги, содержащие менее k входных данных.

В вашем первом случае вы рисуете два круга радиус-10: первый содержит все входные данные, кроме 70, второй содержит только 70. Ваш критерий обнаружения аномальных кругов должен поймать 70-содержащий, который должен быть простым. Во втором случае вы рисуете три круга радиусом-10. Опять же, критерий, который учитывает только 70, должен быть легко сформулирован.

Если бы я собирался сделать это с нуля, не выясняя, как называется проблема (и это, вероятно, хорошо известная проблема с хорошими известными решениями), я бы начал с сортировки входных данных, что, вероятно, будет очень полезно, так как это одномерная проблема. Затем, я бы, вероятно, запустил скользящее окно размера 2R на входах и вычислил частоту перемещения в каждом потенциальном барицентре (пропуская дубликаты и пропуски), сохраняя этот ряд частот отдельно. Затем я жадно помещал бы окна в местах с самыми высокими частотами в первую очередь так, чтобы они не перекрывали друг друга, пока все входы не будут покрыты. Затем я бы идентифицировал любые входные данные, которые были покрыты кругами с частотой перемещения, меньшей некоторой отсечки, связанной со средней частотой движения выбранных окон; например, рассмотрим в качестве аномального все входные данные, покрытые кружками, которые охватывают вдвое меньше входных данных или меньше по сравнению со средним значением, охватываемым всеми кружками.

Пример: 

INPUT:  20, 20, 21, 31, 24, 20, 70, 21, 31, 24, 20, 20, 21, 31, 24, 20, 20, 21, 31, 24

SORTED: 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 24, 24, 24, 24, 31, 31, 31, 31, 70

WINDOW MOVING FREQUENCY:
20: 15
21: 19
(detects gap, jumps)
60: 1
(detects gap, jumps, ends)

WINDOW #1: [11,31]: 19
WINDOW #2: [50, 70]: 1

AVERAGE: 10
50% AVERAGE: 5
WINDOW #1 OVER CUTOFF
WINDOW #2 UNDER CUTOFF

Пример: 

INPUT:  20, 20, 21, 31, 24, 20, 70, 21, 31, 24, 120, 120, 121, 131, 124, 120, 120, 121, 131, 124

SORTED: 20, 20, 20, 21, 21, 24, 24, 31, 31, 70, 120, 120, 120, 120, 121, 121, 124, 124, 131, 131

WINDOW MOVING FREQUENCY:
20: 7
(detects gap, jumps)
60: 1
(detects gap, jumps)
110: 4
111: 6
(detects gap, jumps)
114: 8
(detects gap, jumps)
121: 10

WINDOW #1: [111, 131]: 10
WINDOW #2: [10, 30]: 7
WINDOW #3: [50, 70]: 1

AVERAGE: 6
50% AVERAGE: 3

WINDOW #1 ABOVE CUTOFF
WINDOW #2 ABOVE CUTOFF
WINDOW #3 BELOW CUTOFF
...