第一个唯一数字
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
在初始化过程中,如果输入列表中存在重复的数字,它们会如何被处理?具体地说,第一个出现的数字是否会留在列表中,而后续的重复数字是否会从列表中移除,还是根本不添加进列表?
▷🦆
在`showFirstUnique`方法中,索引`idx`在跳过已标记为重复的元素后是否会重新设置回较小的值,还是会一直增加?这会如何影响性能?
▷🦆
当`add`方法添加一个已存在于字典但未在列表中的元素时(例如,之前被认为是独一无二然后重复),该元素会被再次添加到列表中吗?
▷🦆
该算法在处理大量重复元素时的性能如何?特别是当`showFirstUnique`方法需要频繁跳过这些元素时?
▷