leetcode
leetcode 1901 ~ 1950
数组中紧跟 key 之后出现最频繁的数字

数组中紧跟 key 之后出现最频繁的数字

难度:

标签:

题目描述

代码结果

运行时间: 24 ms, 内存: 16.3 MB


// Java Stream Solution
// 题目思路:
// 1. 使用Stream API统计key后一个元素的出现次数
// 2. 通过Collectors.groupingBy和Collectors.counting收集数据
// 3. 找到出现次数最多的元素并返回

import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int mostFrequentTarget(int[] nums, int key) {
        Map<Integer, Long> countMap = IntStream.range(0, nums.length - 1)
            .filter(i -> nums[i] == key)
            .mapToObj(i -> nums[i + 1])
            .collect(Collectors.groupingBy(t -> t, Collectors.counting()));
        return countMap.entrySet().stream()
            .max(Map.Entry.comparingByValue())
            .get()
            .getKey();
    }
}

解释

方法:

这个解法使用了一个字典来记录每个可能的target(即紧跟在key后面的数字)的出现次数。遍历数组时,每当发现一个元素等于key时,就查看它后面的元素(target),并在字典中更新该target的计数。同时,我们持续跟踪最大出现次数及对应的数字,如果当前target的计数超过了之前的最大计数,就更新最大计数和结果变量。这种方法确保了我们在一次遍历中即可找到答案。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在解法中,如果数组的长度非常小,例如只包含一个`key`或者`key`后没有其他元素,这种情况下该如何处理?
在这种情况下,当数组只包含一个`key`或者在`key`之后没有其他元素时,后续的代码将无法找到有效的`target`,因为`target`是`key`后面的元素。如果代码尝试访问不存在的`target`(例如数组只有一个元素或`key`是数组的最后一个元素),则不会有任何`target`被添加到字典中。程序在结束遍历后,会检查`result`变量,如果`result`仍然是`None`,则意味着没有找到有效的`target`。这种情况下,函数可以返回`None`或者一个特定的错误值或提示信息,表示无法找到符合条件的`target`。
🦆
为什么选择使用字典来记录target的出现次数而不是其他数据结构,例如数组或计数排序?
使用字典(哈希表)来记录`target`的出现次数是因为字典提供了快速的查找、插入和更新操作,这些操作的平均时间复杂度是O(1)。与之相比,如果使用数组或计数排序,我们可能需要事先知道`target`可能的范围(例如最大值和最小值),以便分配足够的空间进行计数,这在不知道`target`范围的情况下是不可行的。此外,如果`target`的值域非常大,但实际出现的`target`种类较少,则使用数组会导致大量空间浪费。因此,字典在这种情况下是更灵活和空间效率更高的选择。
🦆
在遍历数组时,你是如何确保在更新字典时不会遇到数组越界的问题?
在遍历数组时,代码通过只遍历到数组的倒数第二个元素(即使用`for i in range(n - 1)`)来确保不会遇到数组越界的问题。这种遍历方式保证了当我们在代码中引用`nums[i + 1]`时,`i + 1`总是一个有效的索引。如果`i`等于`n-1`(数组的最后一个索引),则`i + 1`会超出数组界限,但由于循环的限制,这种情况不会发生。
🦆
当`key`在数组中连续出现时,例如`[key, key, target]`,这种情况下的输出是否会受到影响?
当`key`连续出现时,例如在数组`[key, key, target]`中,每个`key`后面的元素都被视为`target`。在这个例子中,第一个`key`后面直接是另一个`key`,所以第二个`key`也被计为一个`target`。随后,第二个`key`后面是`target`,这个`target`也会被计入统计中。因此,这种情况下的输出会包括所有紧跟在`key`后面的元素的统计,但不会对结果的正确性产生影响。只要逻辑正确地处理每一个`key`后面的元素,即使`key`连续出现也能正确统计每个`target`的出现次数。

相关问题