359. 日志速率限制器

Posted on | In
Words count in article: 755 | Reading time ≈ 3

题目

请你设计一个日志系统，可以流式接收日志以及它的时间戳。

该日志会被打印出来，需要满足一个条件：当且仅当日志内容 在过去的 10 秒钟内没有被打印过。

给你一条日志的内容和它的时间戳（粒度为秒级），如果这条日志在给定的时间戳应该被打印出来，则返回 true，否则请返回 false。

要注意的是，可能会有多条日志在同一时间被系统接收。

示例1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Logger logger = new Logger();

// 日志内容 "foo" 在时刻 1 到达系统
logger.shouldPrintMessage(1, "foo"); returns true; 

// 日志内容 "bar" 在时刻 2 到达系统
logger.shouldPrintMessage(2,"bar"); returns true;

// 日志内容 "foo" 在时刻 3 到达系统
logger.shouldPrintMessage(3,"foo"); returns false;

// 日志内容 "bar" 在时刻 8 到达系统
logger.shouldPrintMessage(8,"bar"); returns false;

// 日志内容 "foo" 在时刻 10 到达系统
logger.shouldPrintMessage(10,"foo"); returns false;

// 日志内容 "foo" 在时刻 11 到达系统
logger.shouldPrintMessage(11,"foo"); returns true;

解法

解法一：

借助HashMap

如果当前日志不在map中，将日志加入map中，返回true；

如果当前日志在map中，判断时间，超过10s，返回true，同时更新最新的时间；否则返回false，

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Logger {

	private Map<String, Integer> map;
	
    /** Initialize your data structure here. */
    public Logger() {
    	map = new HashMap<>();
    }
    
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    public boolean shouldPrintMessage(int timestamp, String message) {
    	if (!map.containsKey(message)) {
    		map.put(message, timestamp);
    		return true;
    	} else {
    		int oldTime = map.get(message);
    		if (timestamp - oldTime < 10) {
    			return false;
    		} else {
                map.put(message, timestamp);
                return true;
            }
    	}
    }
}

解法二：

借助HashMap。

遍历数组，在遍历的过程中，判断该数字是否已经存在HashMao中了。

如果已经存在，挨个计算它之前的索引和当前索引差是否超过k，没有则返回true；

否则把当前索引加入索引列表中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean containsNearbyDuplicate(int[] nums, int k) {
		Map<Integer, List<Integer>> map = new HashMap<>();

		for (int i = 0; i < nums.length; i++) {
			if (map.containsKey(nums[i])) {
				List<Integer> list = map.get(nums[i]);
				for (int num : list) {
					if (k >= Math.abs(num - i)) {
						return true;
					} 
				}
				map.get(nums[i]).add(i);
			} else {
				List<Integer> list = new ArrayList<>();
				list.add(i);
				map.put(nums[i], list);
			}
		}
		return false;
	}

解法三：

使用HashSet。

遍历数组，对于每个元素做以下操作：

  1. 在散列表中搜索当前元素，如果找到了就返回 true。
  2. 在散列表中插入当前元素。
  3. 如果当前散列表的大小超过了 kkk， 删除散列表中最旧的元素。

返回false

1
2
3
4
5
6
7
8
9
10
11
12
public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; ++i) {
        if (set.contains(nums[i])) return true;
        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}

0%