Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
Solution:
Keep tracking the past k elements by forming a BST for these k numbers. When new element coming, search BST to see if a target number exist. Remove the furthest element out of BST and insert current element to BST.
Here, we need to use some nice features provided by STL. In STL, a BST is implemented as a "set". In set, there exist a functionality that can search the smallest number that is greater than search key. by using this feature, we can determine if there exist a number that is in the range of [key-t, key+t].:
No comments:
Post a Comment