А>Собственно, вопрос: нельзя ли как-нибудь избавиться от таблицы T с размером O(N)?
А может сам набор данных перемешать случайным образом, а потом выбирать по порядку? Тогда только счётчик придётся сохранять