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

Question

Я хочу выбрать верхний «диапазон» карт на основе процента. У меня все мои возможные 2 карточные руки организованы в массив в порядке силы руки, например:

AA, KK, AKsuited, QQ, AKoff-suit ...

Я выбрал верхние 10% раздач, умножив длину массива карт на процент, который дал бы мне индекс последней карты в массиве. Тогда я бы просто сделал копию подмассива:

Arrays.copyOfRange(cardArray, 0, 16);

Однако теперь я понимаю, что это неправильно, потому что существует больше возможных комбинаций, скажем, Ace King off-масти - 12 комбинаций (т.е. туз одной масти и короля другой масти), чем есть комбинации, скажем, пара тузов - 6 комбинаций.

Когда я выбираю верхние 10% рук, поэтому я хочу, чтобы они основывались на верхних 10% рук пропорционально общему количеству комбинаций из двух карт - 52 выбирают 2 = 1326.

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

6, 12, 16, 22

потому что есть 6 комбинаций AA, 6 комбинаций KK, 4 комбинации AKsuited, 6 комбинаций QQ.

Тогда я мог бы выполнить бинарный поиск, который выполняется во время BigOh (log n). Другими словами, я мог бы умножить общее количество комбинаций (1326) на процент, найти первый индекс, меньший или равный этому числу, и это было бы индексом исходного массива, который мне нужен.

Интересно, есть ли способ сделать это в постоянное время?

Answer 1

Как предположил Гро, если предварительное вычисление и накладные расходы памяти позволяют, было бы более эффективно создать 6 копий AA, 6 копий KK и т. Д. И сохранить их в отсортированном массиве. Тогда вы можете запустить свой оригинальный алгоритм в этом правильно взвешенном списке.

Лучше всего, если количество запросов велико.

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

Answer 2

здесь было похожее обсуждение Алгоритм выбора элементов с увеличенным количеством элементов В качестве комментария к моему ответу (в основном то, что вы хотите сделать со своим списком карточек), кто-то предложил конкретную структуру данных http://en.wikipedia.org/wiki/Fenwick_tree

Кроме того, убедитесь, что ваша структура данных сможет обеспечить эффективный доступ, скажем, к диапазону от верхних 5% до 15% (однако это не совет по кодированию;).