What is the primary approach to solving the 'Find All Lonely Numbers in the Array' problem?

The primary approach involves using a hash table to count occurrences and check adjacent numbers, ensuring efficient lookup and single-pass scanning.

How can you improve the time complexity for the 'Find All Lonely Numbers' problem?

By using a hash table for counting and checking adjacent values, the solution can be optimized to O(n) time complexity, where n is the array length.

What should you do when dealing with edge cases in this problem?

Edge cases like arrays with a single element or duplicates should be handled by ensuring the lonely number condition is still met and no adjacent numbers exist.

Can the solution for finding lonely numbers be adapted for sorted arrays?

Yes, a sorted array can simplify the checking of adjacent values, allowing for potential optimizations that reduce the space complexity.

How does GhostInterview help in solving the 'Find All Lonely Numbers in the Array' problem?

GhostInterview offers hints for optimizing your approach and checks for edge cases, ensuring a correct and efficient solution using array scanning and hash table lookup.

#2150

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个整数数组 nums 。如果数字 x 在数组中仅出现一次，且没有相邻数字（即， x + 1 和 x - 1 ）出现在数组中，则认为数字 x 是孤独数字。返回 nums 中的所有孤独数字。你可以按任何顺序返回答案。示例 1：输入： nums = [10,6,5,8] 输…

数组哈希表计数

题目描述

给你一个整数数组 nums 。如果数字 x 在数组中仅出现一次，且没有相邻数字（即，x + 1 和 x - 1）出现在数组中，则认为数字 x 是 孤独数字 。

返回 nums 中的所有孤独数字。你可以按 任何顺序 返回答案。

示例 1：

输入：nums = [10,6,5,8]
输出：[10,8]
解释：
- 10 是一个孤独数字，因为它只出现一次，并且 9 和 11 没有在 nums 中出现。
- 8 是一个孤独数字，因为它只出现一次，并且 7 和 9 没有在 nums 中出现。
- 5 不是一个孤独数字，因为 6 出现在 nums 中，反之亦然。
因此，nums 中的孤独数字是 [10, 8] 。
注意，也可以返回 [8, 10] 。

示例 2：

输入：nums = [1,3,5,3]
输出：[1,5]
解释：
- 1 是一个孤独数字，因为它只出现一次，并且 0 和 2 没有在 nums 中出现。
- 5 是一个孤独数字，因为它只出现一次，并且 4 和 6 没有在 nums 中出现。
- 3 不是一个孤独数字，因为它出现两次。
因此，nums 中的孤独数字是 [1, 5] 。
注意，也可以返回 [5, 1] 。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁶

lightbulb

解题思路

方法一：哈希表

我们用一个哈希表 $\textit{cnt}$ 记录每个数字出现的次数，然后遍历哈希表，对于每个数字及其出现次数 $(x, v)$ ，如果 $v = 1$ 且 $\textit{cnt}[x - 1] = 0$ 且 $\textit{cnt}[x + 1] = 0$ ，则 $x$ 是一个孤独数字，将其加入答案数组中。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

class Solution:
    def findLonely(self, nums: List[int]) -> List[int]:
        cnt = Counter(nums)
        return [
            x for x, v in cnt.items() if v == 1 and cnt[x - 1] == 0 and cnt[x + 1] == 0
        ]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for an efficient way to handle large arrays by minimizing unnecessary iterations.
question_mark
Test for understanding of hash table usage in combination with array scanning techniques.
question_mark
Assess the candidate's ability to optimize for time complexity without overcomplicating the solution.

warning

常见陷阱

外企场景

error
Overcomplicating the problem by using nested loops or inefficient searching techniques.
error
Forgetting to check both the presence of a number and its adjacent values in the array.
error
Not handling edge cases such as arrays with a single element or duplicate values properly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if you need to find lonely numbers in a sorted array?
arrow_right_alt
How would the solution change if the numbers in the array can be negative?
arrow_right_alt
Can you optimize the solution further if the array is known to have a limited range of numbers?

help

常见问题

外企场景

继续练习

#2131 连接两字母单词得到的最长回文串 #2170 使数组变成交替数组的最少操作数 #2190 数组中紧跟 key 之后出现最频繁的数字