Medium

题目描述

给你一个整数数组 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^5
  • 0 <= nums[i] <= 10^6

解题思路

这道题需要找出数组中的"孤独数字"，即满足两个条件的数字：

  1. 该数字在数组中只出现一次
  2. 该数字的相邻数字（x-1 和 x+1）都不在数组中

解法分析：

方法一：哈希表计数（推荐）

  • 首先用哈希表统计每个数字的出现次数
  • 然后遍历哈希表，对于出现次数为1的数字，检查其相邻数字是否存在
  • 如果相邻数字都不存在，则该数字是孤独数字

方法二：集合查找

  • 将所有数字放入集合中，便于快速查找
  • 遍历数组，对于每个数字，检查：
    • 该数字在原数组中的出现次数是否为1
    • 相邻数字是否不在集合中

两种方法时间复杂度相同，但方法一更直观，只需要一次遍历哈希表即可完成判断。

实现要点：

  • 使用哈希表/字典统计频次
  • 检查相邻数字时注意边界情况
  • 最终结果可以按任意顺序返回

代码实现

class Solution {
public:
    vector<int> findLonely(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        vector<int> result;
        for (auto& [num, freq] : count) {
            if (freq == 1 && count.find(num - 1) == count.end() && count.find(num + 1) == count.end()) {
                result.push_back(num);
            }
        }
        
        return result;
    }
};

class Solution:
    def findLonely(self, nums: List[int]) -> List[int]:
        count = Counter(nums)
        
        result = []
        for num, freq in count.items():
            if freq == 1 and (num - 1) not in count and (num + 1) not in count:
                result.append(num)
        
        return result

public class Solution {
    public IList<int> FindLonely(int[] nums) {
        var count = new Dictionary<int, int>();
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        var result = new List<int>();
        foreach (var kvp in count) {
            int num = kvp.Key;
            int freq = kvp.Value;
            if (freq == 1 && !count.ContainsKey(num - 1) && !count.ContainsKey(num + 1)) {
                result.Add(num);
            }
        }
        
        return result;
    }
}

var findLonely = function(nums) {
    const count = new Map();
    
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    const result = [];
    
    for (const [num, freq] of count) {
        if (freq === 1 && !count.has(num - 1) && !count.has(num + 1)) {
            result.push(num);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组统计频次，然后遍历哈希表检查条件
空间复杂度O(n)哈希表存储数字频次，最坏情况下存储所有不同的数字

相关题目