leetcode
leetcode 951 ~ 1000
最大唯一数

最大唯一数

难度:

标签:

题目描述

代码结果

运行时间: 27 ms, 内存: 16.2 MB


/*
 * Leetcode 1133: Largest Unique Number
 * 
 * Given an array of integers, return the largest integer that only occurs once. If no integer occurs once, return -1.
 * 
 * Approach using Java Stream:
 * 1. Use a HashMap to count the occurrences of each number.
 * 2. Use streams to filter out numbers that appear more than once and find the maximum of the remaining numbers.
 * 3. If no such number exists, return -1.
 */

import java.util.HashMap;
import java.util.Map;
import java.util.OptionalInt;
import java.util.stream.IntStream;

public class LargestUniqueNumberStream {
    public int largestUniqueNumber(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        OptionalInt max = countMap.entrySet().stream()
            .filter(entry -> entry.getValue() == 1)
            .mapToInt(Map.Entry::getKey)
            .max();
        return max.orElse(-1);
    }
}

解释

方法:

这个题解的思路如下: 1. 首先,使用一个字典 `freq` 来统计数组中每个数字出现的频率。遍历数组 `nums`,对于每个数字,如果它已经在字典中,则将其对应的频率加 1;否则,将其频率初始化为 1。 2. 接下来,遍历字典 `freq`,找到仅出现一次且值最大的数字。初始化一个变量 `max_unique` 为 -1,表示当前找到的最大唯一数。对于字典中的每个键值对,如果该数字的频率为 1 且大于当前的 `max_unique`,则更新 `max_unique` 为该数字。 3. 最后,返回 `max_unique` 作为结果,即为仅出现一次的最大整数。如果不存在这样的数,则返回初始值 -1。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在统计频率时,如果数组非常大,这种方法的内存占用会如何影响性能?
在统计频率时,使用字典来存储每个数字的频率。如果数组非常大,内存占用主要取决于数组中不同数字的数量。在最坏的情况下,即数组中每个元素都不相同,字典将需要存储与数组长度相等的条目数,这将显著增加内存使用。对于非常大的数组,这可能导致内存不足的问题,尤其是在内存资源有限的环境中。改善内存使用的一种方式可能是使用更内存效率高的数据结构,如计数排序或位图,尤其是当元素的范围已知且有限时。
🦆
该算法是否考虑了所有数字都重复出现的极端情况?如果数组中没有唯一数字,返回值是否正确处理了这种情况?
算法已经考虑了所有数字都重复出现的情况。在算法中,如果所有数字都至少重复一次,那么字典遍历时不会找到任何频率为1的数字,因此变量 `max_unique` 将保持其初始化的值 -1。这意味着函数将正确返回 -1,表示数组中没有唯一数字。这符合题目要求的正确处理方式。
🦆
在字典 `freq` 遍历时,你是如何确保找到的是最大的唯一数而不只是任意一个唯一数?
在遍历字典 `freq` 时,算法检查每个条目的频率是否为1(表示数字唯一),并与当前存储的最大唯一数 `max_unique` 比较。如果找到的唯一数字大于 `max_unique`,则更新 `max_unique` 的值。这保证了在遍历结束时,`max_unique` 存储的是所有唯一数字中的最大值。因此,通过这种方式,算法确保最终找到并返回的是最大的唯一数。
🦆
如果输入数组 `nums` 是空的,这个方法有没有处理这种边界情况?如果没有,应该如何修改代码以处理空数组输入?
当前的实现已经可以正确处理空数组的情况。当输入数组 `nums` 为空时,字典 `freq` 也将为空,因此在遍历字典时不会有任何操作执行。变量 `max_unique` 将保持其初始值 -1,然后被返回。因此,该方法已正确处理空数组输入的情况,无需进行修改。

相关问题