找出数组中的所有孤独数字
难度:
标签:
题目描述
代码结果
运行时间: 153 ms, 内存: 37.5 MB
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class LonelyNumbersStream {
/**
* This method finds all lonely numbers in the given array using Java Streams.
* A lonely number appears only once in the array and has no neighboring numbers.
* @param nums the input array of integers
* @return a list of lonely numbers
*/
public List<Integer> findLonely(int[] nums) {
Map<Integer, Long> countMap = Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(n -> n, Collectors.counting()));
return Arrays.stream(nums)
.filter(num -> countMap.get(num) == 1 && !countMap.containsKey(num - 1) && !countMap.containsKey(num + 1))
.distinct()
.collect(Collectors.toList());
}
public static void main(String[] args) {
LonelyNumbersStream lns = new LonelyNumbersStream();
int[] nums = {10, 6, 5, 8};
System.out.println(lns.findLonely(nums)); // Output: [10, 8]
}
}
解释
方法:
该题解首先使用Counter来统计数组nums中每个数字出现的次数。然后,遍历这个计数器。对于每个键值对(即数字及其出现次数),检查该数字是否只出现一次(即次数为1),并且其相邻的数字(即x-1和x+1)是否没有出现在数组中。如果这些条件都满足,那么这个数字就被认为是孤独的,并将其添加到输出列表中。最后,返回这个列表。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在使用Counter统计数组中每个数字出现次数的基础上,算法如何确保检查相邻数字是否存在的效率?
▷🦆
为什么选择Counter而不是其他数据结构,如字典或集合,来实现这个算法?
▷🦆
算法中提到对于每个数字最多进行3次哈希表查找,这是否包括了对自己的查找?如果是,为什么需要检查自己?
▷🦆
如果输入数组是空数组或只包含一个元素,这个算法会如何处理?
▷