Sword finger offer II 057. the difference between the value and the subscript is within the given range (medium array bucket sort sliding window TreeSet)

The finger of the sword Offer II 057. The difference between the value and the subscript is within the given range

Please implement a MyCalendar Class to store your schedule . If there is no other schedule for the time to be added , You can store this new schedule .

MyCalendar There is one book(int start, int end) Method . It means in start To end Add a schedule in time , Be careful , The time here is a half open interval , namely [start, end), The set of real Numbers x For the range of , start <= x < end.

When there is some time overlap between the two schedules （ For example, both schedules are in the same time ）, There will be repeat bookings .

Every time you call MyCalendar.book When the method is used , If the schedule can be successfully added to the calendar without causing duplicate bookings , return true. otherwise , return false And don't add the schedule to the calendar .

Please follow the steps below to call MyCalendar class : MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example :

Input :
[“MyCalendar”,“book”,“book”,“book”]
[[],[10,20],[15,25],[20,30]]
Output : [null,true,false,true]
explain :
MyCalendar myCalendar = new MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false , The second schedule cannot be added to the calendar , Because of time 15 It has been scheduled by the first schedule
MyCalendar.book(20, 30); // returns true , The third schedule can be added to the calendar , Because the first schedule doesn't include time 20

Tips ：

Each test case , call MyCalendar.book The function is no more than 1000 Time .
0 <= start < end <= 109

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/fi9suh
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Method 1 ： Use TreeSet
Time complexity O(nlogk)
utilize TreeSet Characteristics of , Traversal array , stay TreeSet Add a size of k The number in the sliding window of , Every number traversed , utilize ceiling Methods and floor Methods find the number that meets the condition , Go back when you find it true, If you don't find it, continue to traverse .
We need to pay attention to TreeSet Parameters of should use Long type , Because the basic type int It can't be null.
Method 2 ： Hash table bucket sorting idea
Time complexity O(n)
Using the idea of bucket sorting , Because the difference between the two numbers required is less than or equal to t, You can prepare k A barrel , The size of each bucket is t + 1, Such as 0 The storage size of bucket No. is 0~t The number of ,1 No. barrel storage t + 1 To 2t + 1 The number of , The number of barrels can be used num / (t + 1) Come to , In the process of traversal, if the number traversed belongs to the bucket （ Number id） It already exists , Then it means that the difference between the two values is less than or equal to t, If id Bucket does not exist , Then judge the adjacent id - 1 The barrel and id + 1 Whether the difference between the number of barrels and the current number is less than or equal to t.
After clarifying the idea , The other thing to note is that ：1、 The number may be negative , For negative numbers , Numbers -t - 1 To -1 Should be placed in -1 In No.1 barrel ,-2t-2 To -t-2 Should be placed in -2 In No.1 barrel , The number of negative barrels can be used (num + 1)/ (t + 1) - 1 Come to ;2、 The number may be out of bounds , If t = 2^31 - 1,t + 1 Will cross the border , Empathy num + 1 It may also cross the border , So the type definition of all numbers should be defined as long type .

Answer key （Java）

Method 1 ： Use TreeSet

class Solution {
    
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
    
            Long lower = set.floor((long)nums[i]);
            if (lower != null && (long)nums[i] - lower <= t) {
    
                return true;
            }
            Long higher = set.ceiling((long)nums[i]);
            if (higher != null && higher - (long)nums[i] <= t) {
    
                return true;
            }
            set.add((long)nums[i]);
            if (i >= k) {
    
                set.remove((long)nums[i - k]);
            }
        }
        return false;
    }
}

Method 2 ： Hash table bucket sorting idea

class Solution {
    
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    
        Map<Long, Long> map = new HashMap<>();
        Long size = (long)t + 1;
        for (int i = 0; i < nums.length; i++) {
    
            Long num = (long)nums[i];
            Long id = getId(num, size);
            if (map.containsKey(id) ||
            (map.containsKey(id - 1) && num - map.get(id - 1) <= t) ||
            (map.containsKey(id + 1) && map.get(id + 1) - num <= t)) {
    
                return true;
            }
            map.put(id, num);
            if (i >= k) {
    
                map.remove(getId((long)nums[i - k], size));
            }
        }
        return false;
    }

    private Long getId(Long num, Long size) {
    
        return num >= 0 ? num / size : (num + 1) / size - 1;
    }
}