Easy

题目描述

给你一个整数数组 nums。如果一个数组是 base[n] 的排列，我们就认为它是好的。

base[n] = [1, 2, ..., n - 1, n, n]（换句话说，它是一个长度为 n + 1 的数组，其中包含 1 到 n - 1 恰好一次，加上两个 n）。例如，base[1] = [1, 1] 和 base[3] = [1, 2, 3, 3]。

如果给定的数组是好的，返回 true，否则返回 false。

注意： 整数的排列表示这些数字的一种排列。

示例 1：

输入：nums = [2, 1, 3]
输出：false
解释：由于数组的最大元素是 3，这个数组可能是 base[n] 的排列的唯一候选 n 是 n = 3。然而，base[3] 有四个元素，但数组 nums 有三个。因此，它不可能是 base[3] = [1, 2, 3, 3] 的排列。所以答案是 false。

示例 2：

输入：nums = [1, 3, 3, 2]
输出：true
解释：由于数组的最大元素是 3，这个数组可能是 base[n] 的排列的唯一候选 n 是 n = 3。可以看出 nums 是 base[3] = [1, 2, 3, 3] 的排列（通过交换 nums 中的第二个和第四个元素，我们得到 base[3]）。因此，答案是 true。

示例 3：

输入：nums = [1, 1]
输出：true
解释：由于数组的最大元素是 1，这个数组可能是 base[n] 的排列的唯一候选 n 是 n = 1。可以看出 nums 是 base[1] = [1, 1] 的排列。因此，答案是 true。

示例 4：

输入：nums = [3, 4, 4, 1, 2, 1]
输出：false
解释：由于数组的最大元素是 4，这个数组可能是 base[n] 的排列的唯一候选 n 是 n = 4。然而，base[4] 有五个元素，但数组 nums 有六个。因此，它不可能是 base[4] = [1, 2, 3, 4, 4] 的排列。所以答案是 false。

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 200

解题思路

要判断数组是否是好数组，我们需要理解好数组的定义：base[n] = [1, 2, ..., n-1, n, n]，即包含 1 到 n-1 各一次，以及两个 n。

解题思路：

  1. 确定 n 值：找到数组中的最大值，这个最大值必须是 n。因为好数组中最大的数字就是 n，且出现两次。

  2. 长度检查：好数组 base[n] 的长度是 n+1。因此，如果 nums.length != n+1，直接返回 false。

  3. 频次统计：使用哈希表统计每个数字的出现次数：

    • 数字 1 到 n-1 应该各出现 1 次
    • 数字 n 应该出现 2 次
    • 不应该有其他数字

  4. 验证频次：遍历哈希表，检查每个数字的出现次数是否符合要求。

这种方法的时间复杂度是 O(n)，空间复杂度是 O(n)，是最直接有效的解法。

推荐解法： 哈希表频次统计法，代码简洁且易于理解。

代码实现

class Solution {
public:
    bool isGood(vector<int>& nums) {
        int n = *max_element(nums.begin(), nums.end());
        
        if (nums.size() != n + 1) {
            return false;
        }
        
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        for (int i = 1; i < n; i++) {
            if (count[i] != 1) {
                return false;
            }
        }
        
        return count[n] == 2;
    }
};

class Solution:
    def isGood(self, nums: List[int]) -> bool:
        n = max(nums)
        
        if len(nums) != n + 1:
            return False
        
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1
        
        for i in range(1, n):
            if count.get(i, 0) != 1:
                return False
        
        return count.get(n, 0) == 2

public class Solution {
    public bool IsGood(int[] nums) {
        int n = nums.Max();
        
        if (nums.Length != n + 1) {
            return false;
        }
        
        Dictionary<int, int> count = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
        }
        
        for (int i = 1; i < n; i++) {
            if (!count.ContainsKey(i) || count[i] != 1) {
                return false;
            }
        }
        
        return count.ContainsKey(n) && count[n] == 2;
    }
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isGood = function(nums) {
    const n = Math.max(...nums);
    
    if (nums.length !== n + 1) {
        return false;
    }
    
    const count = new Array(n + 1).fill(0);
    
    for (const num of nums) {
        if (num > n) {
            return false;
        }
        count[num]++;
    }
    
    for (let i = 1; i < n; i++) {
        if (count[i] !== 1) {
            return false;
        }
    }
    
    return count[n] === 2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组找最大值，再遍历数组统计频次，最后验证频次
空间复杂度O(n)哈希表存储数字频次，最多存储 n 个不同的数字