(LeetCode) содержит повторяющиеся III

Question

Дан массив целых чисел, выяснить, есть ли два различных индексы я и J в массиве таким образом, чтобы разница между Nums [я] и НУМС [у] не больше t, а разница между i и j не превышает k.

Hello!

Я, как бы честно, не сомневаюсь в этом вопросе. Решения, представленные в дискуссионном форуме (LeetCode) для этого вопроса, не дали большого объяснения/мыслительного процесса относительно того, как его решить. Я предпочел бы полностью понять технику решения проблемы, чем полный код реализации, предоставленный мне. Я чувствую, что это лучший способ узнать.

Итак, ключом здесь является использование TreeSet (Java) для решения этой проблемы. Я предполагаю, что здесь будут полезны методы пола и потолка.

Буду признателен, если есть кто-нибудь, что может дать мне немного подсказки/подсказки, чтобы подойти к этой проблеме. Псевдокод также приветствуется! Мне не нужен полный код реализации, как я уже говорил. Просто отправная точка была бы замечательной! :)

Спасибо!

EDIT: Я также работаю над этим, тем временем! Итак, если я в конечном итоге дойду до ответа, я отправлю его здесь для дальнейшего использования. :)

Answer 1

Первая реализация, которая приходит на ум, - это всего лишь два для петель, с одним вложенным.

Внутри внутренней петли проверить логику абс (nums [i] -nums [j]) < = t и abs (i-j) < = k.

Внешний контур: я от 0 до п

Внутренняя петля: J от + 1 до п

Answer 2

Вопрос довольно старый, но ОП до сих пор не отправил его/ее ответ ...
Я попытаюсь объяснить людям, которые также наткнулись на этот вопрос.

Следующий ответ основан на ведра и время сложность О (п).

Основная идея - использовать скользящее окно, ширина которого равна k. Наше внимание будет ограничено в этом окне, так что разница между i и j (индексами) в этом окне не может быть больше k. И мы проверяем наличие двух чисел в этом окне с разницей не более t. Если таких чисел, то мы закончили. В противном случае наше окно будет двигаться вперед на один шаг, и мы снова проверим.

Теперь вопрос в том, как мы проверяем, если есть два таких номера в окне. Конечно, мы можем использовать жестокую силу, которая будет O (K^2), тогда весь алгоритм будет O (n * K^2). Если K не велико, мы можем принять это.

Однако, используя ведра, мы можем сделать гораздо лучше!

Всякий раз, когда мы сталкиваемся с числом в окне, мы делим его на (t + 1).Предположим, что результат B, тогда мы поместим его в ведро [B].

Если t = 3, то цифры 0, 1, 2, 3 будут помещены в ведро [0], цифры 4, 5, 6, 7 будут помещены в ведро [1] и 8, 9, 10 , 11 будет помещен в ведро [2] и т. Д. Мы гарантировали, что все числа в одном ковше будут иметь разности, не превышающие t. И еще есть одно: 4 - 2 = 2 < 3 и они находятся в разных ведрах. Да, некоторые числа с разницей меньше t могут быть помещены в разные ковши. В таких случаях, однако, они могут находиться только в соседних ведрах.

Ниже приведен пример:

nums = [1, 5, 17, 6, 8], t = 2, k = 5 

(. Мы не должны беспокоиться о к теперь, так как это то же самое, как длина Nums)

С т = 2, так что всякий раз, когда мы встречаем число в списке, мы делим его на t + 1 (целое число делится) и помещаем его в соответствующее ведро.

1/3 = 0 --> We put 1 in bucket[0] 

5/3 = 1 --> We put 5 in bucket[1] 

Поскольку может быть элементы в ведрах соседних ведра [1], удовлетворяющие требования, мы должны проверить эту. bucket [0] имеет номер 1, но 5 - 1> 3, а еще нет ведра [2], поэтому мы продолжаем.

17/3 = 5 --> We put 17 in bucket[5] 

Нет ведра [4] или ковша [6], поэтому мы продолжаем.

6/3 = 2 --> We put 6 in bucket[2] 

Мы должны проверить номер в ковше [1]: | 5 - 6 | = 1 < 2 поэтому есть такие числа, и мы возвращаем True.

Если мы поместим 8 в ведро [2], то найдем, что в нем уже есть элемент, который равен 6. Поскольку все элементы в одном ковше имеют разности, не большие, чем t, мы делаем.

Итак, чтобы проверить, есть ли два числа с разницей меньше t, мы помещаем каждое число, с которым мы сталкиваемся в ведре. Если в этом ковше уже есть элемент, мы закончили. В противном случае мы проверяем, имеет ли соседние ведра элемент, удовлетворяющий требованию, если этого не происходит, мы продолжаем помещать числа в ведро.

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

Ниже приведен код Python.

if t < 0 or not nums or k <= 0: 
    return False 
buckets = {} 
width = t + 1 

for n, i in enumerate(nums): 
    buck = i // width 
    if buck in buckets: 
     return True 
    else: 
     buckets[buck] = i 
     if buck - 1 in buckets and i - buckets[buck-1] <= t: 
      return True 
     if buck + 1 in buckets and buckets[buck+1] - i <= t: 
      return True 
     if n >= k: 
      del buckets[nums[n-k] // width] 
return False