Мне нужно отсортировать массив случайных уникальных положительных целых чисел размером n тысяч в группы последовательных целых чисел, каждая из которых имеет размер группы k или больше, а затем сгруппировать в дивиденды некоторого произвольного положительного целого числа j.
Другими словами, допустим, я работаю в Chuck E. Cheese, и мы иногда раздаем бесплатные билеты. У меня есть пара сотен тысяч билетов на этаже, и я хочу выяснить, какой сотрудник что раздал, но только для групп билетов, состоящих из последовательных целых чисел, превышающих 500. Каждому сотруднику присвоено случайное число от 0 до 100. им. Это число соответствует тому, какая «партия» билетов была роздана, т. е. билеты с № 000000 по № 001499 были выданы сотрудником 1, билеты с № 001500 по № 002999 были розданы сотрудником 2 и так далее. Большое количество билетов потеряно или отсутствует. Меня интересуют только группы последовательных номеров билетов, превышающие 500.
Как мне быстрее всего разобраться в этой куче?
Редактировать: По просьбе @trincot вот проработанный пример:
У меня есть 150 000 уникальных билетов на этаже в диапазоне от 000000 до 200000 (т.е. отсутствует 50 001 случайный билет из стопки)
Шаг 1: отсортируйте каждый билет от меньшего к большему, используя алгоритм внутренней сортировки.
Шаг 2: просмотрите список билетов один за другим и соберите только билеты с «последовательностью» больше 500. То есть я веду подсчет того, сколько последовательных значений я нашел, и сохраняю только те, у которых количество 500 или выше. Если бы у меня были билеты с № 409 по № 909, но не № 408 или № 1000, я бы сохранил эту группу, но если бы эта группа пропустила билет где-то с № 409 до № 909, я бы выбросил группу и пошел дальше.
Шаг 3: объедините все мои недавно отсортированные группы вместе, каждая из которых имеет размер 500 или больше.
Шаг 4: выясните, какие билеты кому принадлежат, снова просмотрев окончательные числа один за другим, разделив каждое на 1500, округлив до ближайшего целого числа и поместив их в соответствующую стопку, где каждая стопка представляет сотрудника.
Конечным результатом стал набор стопок, сообщающих мне, какие сотрудники выдали более 500 билетов за раз, сколько раз они это делали и с какими билетами.
Образец с номерами: где k == 3 и j = 1500; k - минимальный последовательный целочисленный размер группировки, j - конечный размер группировки интервалов билетов, т.е. 5,6 и 7 попадают в 0-ю группу интервалов размера 1500, а 5996, 5997, 5998, 5999 попадают в третью группу интервалов размера 1500 .
Ввод: [5, 5996, 8111, 1000, 1001, 5999, 8110, 7, 5998, 2500, 1250, 6, 8109, 5997]
Вывод: [ 0: [5, 6, 7] , 3: [5996, 5997, 5998, 5999] , 5: [8109, 8110, 8111] ]
@trincot да, диапазоны известны заранее. Дивиденд — не совсем правильный термин, но я использовал его, потому что в конце я сужаю, какие билеты кому принадлежат, разделив номер билета на 1500 и округлив до ближайшего целого числа. Я обновил вопрос, включив в него номер сотрудника ноль.
Я не очень понимаю, какой результат вы ожидаете. Не могли бы вы предоставить полностью проработанный пример, включая ввод и ожидаемый результат?
@trincot конечно, сейчас обновлю
@trincot Я добавил числовой пример с примерами ввода и вывода. У вас есть предлагаемое решение?
Как бы выглядел ваш вывод, если бы у вас также было 10,11,12 на входе? А что такое "дивиденд" в этом примере?
@trincot новый вывод будет [ 0: [5, 6, 7,10,11,12] , 3: [5996, 5997, 5998, 5999] , 5: [8109, 8110, 8111] ]
10,11 и 12 идут последовательно и соответствуют размеру группы 3 или больше. Чтобы узнать, какому «дивиденду» принадлежит каждое из этих n целых чисел, я применяю следующую формулу: (округлить в меньшую сторону ( n / j )) * j
О, я понял. Я думаю, мы называем это «разделом».
ДА! раздел - гораздо лучшее слово, спасибо @trincot
Вот непроверенный Python для самого быстрого подхода, который я могу придумать. Он вернет только пары первый/последний билет для каждого найденного диапазона интересов.
def grouped_tickets (tickets, min_group_size, partition_size):
tickets = sorted(tickets)
answer = {}
min_ticket = -1
max_ticket = -1
next_partition = 0
for ticket in tickets:
if next_partition <= ticket or max_ticket + 1 < ticket:
if min_group_size <= max_ticket - min_ticket + 1:
partition = min_ticket // partition_size
if partition in answer:
answer[partition].append((min_ticket, max_ticket))
else:
answer[partition] = [(min_ticket, max_ticket)]
# Find where the next partition is.
next_partition = (ticket // partition_size) * partition_size + partition_size
min_ticket = ticket
max_ticket = ticket
else:
max_ticket = ticket
# And don't lose the last group!
if min_group_size <= max_ticket - min_ticket + 1:
partition = min_ticket // partition_size
if partition in answer:
answer[partition].append((min_ticket, max_ticket))
else:
answer[partition] = [(min_ticket, max_ticket)]
return answer
Я проверю/проверю этот подход в ближайшее время, спасибо за помощь.
не совсем., нужно учитывать последовательность. Размер группы должен учитывать общее количество последовательных билетов, а не только расстояние между билетами, т. е. в стопке между максимальным и минимальным номерами могут отсутствовать номера билетов. Я добавил числовой тестовый пример к моему вопросу
@newswiftcoder Не уверен, что вы имеете в виду. Мой код включает билеты в группу только тогда, когда они следуют друг за другом, и поэтому может использовать расстояние для их подсчета. print(grouped_tickets([5 , 5996 , 8111 , 1000 , 1001, 5999 , 8110 , 7 , 5998 , 2500 , 1250 , 6 , 8109 , 5997], 3, 1500))
печатает [(5, 7), (5996, 5999), (8109, 8111)]
, который (после различий в форматах - я печатаю концы диапазона, а вы печатаете все между ними) вывод, который вы сказали, что хотите для своего тестового примера.
@newswiftcoder Можете ли вы привести пример, в котором мой код НЕ дает того результата, о котором вы просили?
этот ввод: print(grouped_tickets([5 , 5996 , 8111 , 1000 , 1001, 5999 , 8110 , 7 , 5998 , 2500 , 1250 , 6 , 8109 , 5997,9,10,11], 3, 1500))
печатает [(5, 7),(9,11),(5996, 5999), (8109, 8111)]
, когда он должен вместо этого печатать [(0,((5, 7),(9,11)), (3,(5996, 5999)), (5,(8109, 8111))]
. Вывод должен включать количество разделов. Ваше решение быстро, хотя
@newswiftcoder Я также обновил код, чтобы получить раздел.
Вот как вы могли бы сделать это в Python:
from collections import defaultdict
def partition(data, k, j):
data = sorted(data)
start = data[0] # assuming data is not an empty list
count = 0
output = defaultdict(list) # to automatically create a partition when referenced
for value in data:
bucket = value // j # integer division
if value % j == start % j + count: # in same partition & consecutive?
count += 1
if count == k:
# Add the k entries that we skipped so far:
output[bucket].extend(list(range(start, start+count)))
elif count > k:
output[bucket].append(value)
else:
start = value
count = 1
return dict(output)
# The example given in the question:
data = [5, 5996, 8111, 1000, 1001, 5999, 8110, 7, 5998, 2500, 1250, 6, 8109, 5997]
print(partition(data, k=3, j=1500))
# outputs {0: [5, 6, 7], 3: [5996, 5997, 5998, 5999], 5: [8109, 8110, 8111]}
Насколько интуитивно понятным было это решение для вас? и есть ли у вас какие-либо советы или ресурсы, которые помогут мне улучшить способ создания алгоритмов? Ваше решение элегантно ответило на это с помощью одного цикла for
, тогда как моему требовалось как минимум три. Спасибо.
Интуиция приходит через действие. Так что для этого я бы лично предложил принять вызовы кода, и их действительно много, особенно те, где после того, как вы отправили решение, вы можете проверить, что отправили другие, и их комментарии. Таких сайтов много, и все они имеют свои плюсы и минусы. Я сам был активен в codewars, leetcode и projecteuler.
Известны ли диапазоны группы заранее? Если в вашем примере вы получите ввод 1499, а затем 1500: тогда вы скажете, что они смежные и принадлежат к одной и той же группе... но вы сделали линию разделения на 1500. Каковы дивиденды? Можете ли вы привести более сложный пример, используя k?