寻找文件副本
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 52 ms, 内存: 23.4 MB
/*
* 思路:
* 使用Java Stream API,我们可以利用Collectors.groupingBy来统计每个id出现的次数。
* 然后我们可以使用filter和findFirst方法来找到第一个出现次数超过1次的id。
*/
import java.util.Arrays;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
public class Solution {
public int findDuplicate(int[] documents) {
Map<Integer, Long> frequencyMap = Arrays.stream(documents)
.boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
return frequencyMap.entrySet().stream()
.filter(entry -> entry.getValue() > 1)
.findFirst()
.map(Map.Entry::getKey)
.orElse(-1); // 如果没有找到重复的id,则返回-1(不应该发生)
}
}
解释
方法:
此题解采用了原地哈希的思路,即利用数组本身作为哈希表使用,以达到空间效率的最大化。具体方法是通过交换数组中的元素,使得每个数字都被放置在其值对应的索引位置上。遍历数组,对于每个位置 i,如果位置 i 上的数 nums[i] 不等于 i,则说明 nums[i] 应该被放在索引 nums[i] 上。在这个过程中,如果发现索引 nums[i] 上已经存在值 nums[i],这意味着找到了一个重复的数字。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在发现`nums[nums[i]] == nums[i]`时可以确定找到了重复的文件id,而不是继续交换?
▷🦆
在原地哈希的过程中,如果数组中存在多个重复的数字,此算法如何确保能够返回任一正确的重复数字?
▷🦆
对于数组中所有元素已经全部在正确位置上时(例如数组已经是有序的),这种算法是否还会有效,并如何处理这种情况?
▷🦆
在遍历和交换元素的过程中,是否存在数组越界的风险,特别是当`nums[i]`的值不在0到n-1的范围内?
▷