leetcode
leetcode 1151 ~ 1200
第一个唯一数字

第一个唯一数字

难度:

标签:

题目描述

代码结果

运行时间: 166 ms, 内存: 56.5 MB


/*
 * 思路:
 * 1. 使用流处理来简化代码。
 * 2. 使用一个LinkedHashMap来维护元素的插入顺序和频率。
 * 3. 遍历数组并填充map。
 * 4. 使用流API来找到第一个值为true的entry。
 */
import java.util.*;
import java.util.stream.*;

public class FirstUniqueNumberStream {
    public int firstUniqNum(int[] nums) {
        LinkedHashMap<Integer, Boolean> map = new LinkedHashMap<>();
        Arrays.stream(nums).forEach(num -> map.put(num, !map.containsKey(num)));
        return map.entrySet().stream()
                   .filter(Map.Entry::getValue)
                   .map(Map.Entry::getKey)
                   .findFirst()
                   .orElse(-1); // 如果没有唯一的数字,返回-1
    }

    public static void main(String[] args) {
        FirstUniqueNumberStream solution = new FirstUniqueNumberStream();
        int[] nums = {2, 3, 5, 2, 3, 4, 5};
        System.out.println(solution.firstUniqNum(nums)); // 输出4
    }
}

解释

方法:

这个解法使用了一个字典 `dup` 和一个列表 `list` 来管理元素。字典用于跟踪每个元素是否重复出现,如果元素在列表中首次出现,则将其存入列表并在字典中标记为 `False` 表示未重复,若元素再次出现,则在字典中更新该元素为 `True` 表示已重复。方法 `showFirstUnique` 通过遍历列表从当前索引 `idx` 开始查找第一个字典中标记为 `False` 的元素,如果找到则返回该元素,否则返回 `-1` 表示无唯一元素。`add` 方法用于添加新元素,如果元素首次出现,则加入列表并在字典中标记为 `False`,若已存在则更新字典标记为 `True`。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在初始化过程中,如果输入列表中存在重复的数字,它们会如何被处理?具体地说,第一个出现的数字是否会留在列表中,而后续的重复数字是否会从列表中移除,还是根本不添加进列表?
在初始化过程中,第一个出现的数字会被添加到列表中并在字典中标记为未重复(False)。如果该数字后续再次出现,它的标记会在字典中更新为已重复(True),但它仍然会留在列表中。后续重复出现的该数字不会被添加到列表中,只更新字典中的重复标记。
🦆
在`showFirstUnique`方法中,索引`idx`在跳过已标记为重复的元素后是否会重新设置回较小的值,还是会一直增加?这会如何影响性能?
`idx`索引在跳过已标记为重复的元素后不会重置回较小的值,它会一直增加。这意味着每次调用`showFirstUnique`方法时,它会从上一次检查结束的地方继续,而不是重新开始。这种处理方式可以减少重复检查已知重复的元素,从而提高查询性能,尤其是在处理大数据时。
🦆
当`add`方法添加一个已存在于字典但未在列表中的元素时(例如,之前被认为是独一无二然后重复),该元素会被再次添加到列表中吗?
如果一个元素在之前已被添加到字典并标记为重复,即使它在列表中存在,`add`方法在再次遇到此元素时不会将其再次添加到列表中。它只会更新字典中的重复状态。因此,重复元素不会被再次添加到列表中。
🦆
该算法在处理大量重复元素时的性能如何?特别是当`showFirstUnique`方法需要频繁跳过这些元素时?
当处理大量重复元素时,该算法的性能可能会受到一定影响。尽管`idx`索引避免了重复检查已知重复的元素,但如果列表中的大部分元素都被标记为重复,`showFirstUnique`方法仍然需要遍历这些元素直到找到非重复的元素或遍历完整个列表。这可能导致较高的时间复杂度,尤其是在元素频繁变为重复的场景中。

相关问题