Сортировать тысячи билетов Chuck E. Cheese

Мне нужно отсортировать массив случайных уникальных положительных целых чисел размером 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] ]

Известны ли диапазоны группы заранее? Если в вашем примере вы получите ввод 1499, а затем 1500: тогда вы скажете, что они смежные и принадлежат к одной и той же группе... но вы сделали линию разделения на 1500. Каковы дивиденды? Можете ли вы привести более сложный пример, используя k?

trincot 16.12.2020 19:25

@trincot да, диапазоны известны заранее. Дивиденд — не совсем правильный термин, но я использовал его, потому что в конце я сужаю, какие билеты кому принадлежат, разделив номер билета на 1500 и округлив до ближайшего целого числа. Я обновил вопрос, включив в него номер сотрудника ноль.

newswiftcoder 16.12.2020 19:32

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

trincot 16.12.2020 19:33

@trincot конечно, сейчас обновлю

newswiftcoder 16.12.2020 19:34

@trincot Я добавил числовой пример с примерами ввода и вывода. У вас есть предлагаемое решение?

newswiftcoder 23.12.2020 02:39

Как бы выглядел ваш вывод, если бы у вас также было 10,11,12 на входе? А что такое "дивиденд" в этом примере?

trincot 23.12.2020 09:42

@trincot новый вывод будет [ 0: [5, 6, 7,10,11,12] , 3: [5996, 5997, 5998, 5999] , 5: [8109, 8110, 8111] ]

newswiftcoder 23.12.2020 13:41

10,11 и 12 идут последовательно и соответствуют размеру группы 3 или больше. Чтобы узнать, какому «дивиденду» принадлежит каждое из этих n целых чисел, я применяю следующую формулу: (округлить в меньшую сторону ( n / j )) * j

newswiftcoder 23.12.2020 13:44

О, я понял. Я думаю, мы называем это «разделом».

trincot 23.12.2020 13:45

ДА! раздел - гораздо лучшее слово, спасибо @trincot

newswiftcoder 23.12.2020 13:48
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
10
69
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Вот непроверенный 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 16.12.2020 22:19

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

newswiftcoder 23.12.2020 03:12

@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)], который (после различий в форматах - я печатаю концы диапазона, а вы печатаете все между ними) вывод, который вы сказали, что хотите для своего тестового примера.

btilly 23.12.2020 03:22

@newswiftcoder Можете ли вы привести пример, в котором мой код НЕ дает того результата, о котором вы просили?

btilly 23.12.2020 03:23

этот ввод: 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 24.12.2020 15:45

@newswiftcoder Я также обновил код, чтобы получить раздел.

btilly 24.12.2020 17:17
Ответ принят как подходящий

Вот как вы могли бы сделать это в 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, тогда как моему требовалось как минимум три. Спасибо.

newswiftcoder 24.12.2020 18:50

Интуиция приходит через действие. Так что для этого я бы лично предложил принять вызовы кода, и их действительно много, особенно те, где после того, как вы отправили решение, вы можете проверить, что отправили другие, и их комментарии. Таких сайтов много, и все они имеют свои плюсы и минусы. Я сам был активен в codewars, leetcode и projecteuler.

trincot 24.12.2020 19:09

Другие вопросы по теме