leetcode
leetcode 1901 ~ 1950
找出数组中的所有孤独数字

找出数组中的所有孤独数字

难度:

标签:

题目描述

代码结果

运行时间: 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本质上是一个字典(哈希表),哈希表的查找操作通常具有O(1)的平均时间复杂度。因此,当算法检查一个数字的相邻数字(x-1和x+1)是否存在于Counter中时,这些操作都是高效的。哈希表结构使得即使在数字范围较大的情况下,查找操作仍然能保持较快的执行速度。
🦆
为什么选择Counter而不是其他数据结构,如字典或集合,来实现这个算法?
Counter是Python中collections模块提供的一个专门用于计数的数据结构,它扩展了普通字典的功能,使其能够更方便地统计元素出现次数。虽然使用普通字典也可以实现相同的功能,Counter提供的接口使得代码更简洁易读。集合不适用于此算法,因为集合只能存储键而不存储键对应的次数。
🦆
算法中提到对于每个数字最多进行3次哈希表查找,这是否包括了对自己的查找?如果是,为什么需要检查自己?
在算法中,提到的最多3次哈希表查找包括对数字自身的查找以及对其相邻数字(x-1和x+1)的查找。对自己的查找是为了确认该数字在数组中确实只出现了一次(即次数为1)。这是确定一个数字是否孤独的关键部分,因为如果一个数字出现多次,即使其相邻数字不在数组中,它也不能被认为是孤独的。
🦆
如果输入数组是空数组或只包含一个元素,这个算法会如何处理?
如果输入数组为空数组,Counter将为空,循环不会执行,直接返回一个空列表。如果数组只包含一个元素,算法会检查这个唯一的数字是否孤独:由于其相邻的数字(x-1和x+1)不在数组中,并且其自身的出现次数为1,因此这个数字会被识别为孤独的并返回这个单一元素的列表。

相关问题