跳转至

2229. 检查数组是否连贯 🔒

题目描述

给你一个整数数组 nums ，如果 nums 是一个 连贯数组 ，则返回 true ，否则返回 false 。

如果数组包含 [x, x + n - 1] 范围内的所有数字（包括 x 和 x + n - 1 ），则该数组为连贯数组；其中 x 是数组中最小的数，n 是数组的长度。

 

示例 1：

输入：nums = [1,3,4,2]
输出：true
解释：
最小值是 1 ，数组长度为 4 。
范围 [x, x + n - 1] 中的所有值都出现在 nums 中：[1, 1 + 4 - 1] = [1, 4] = (1, 2, 3, 4) 。
因此，nums 是一个连贯数组。

示例 2：

输入：nums = [1,3]
输出：false
解释：
最小值是 1 ，数组长度为 2 。 
范围 [x, x + n - 1] 中的所有值没有都出现在 nums 中：[1, 1 + 2 - 1] = [1, 2] = (1, 2) 。 
因此，nums 不是一个连贯数组。

示例 3：

输入：nums = [3,5,4]
输出：true
解释：
最小值是 3 ，数组长度为 3 。
范围 [x, x + n - 1] 中的所有值都出现在 nums 中：[3, 3 + 3 - 1] = [3, 5] = (3，4，5) 。
因此，nums 是一个连贯数组。

 

提示：

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105

解法

方法一：哈希表

我们可以用一个哈希表 \(\textit{s}\) 来存储数组 \(\textit{nums}\) 中的所有元素，用两个变量 \(\textit{mi}\) 和 \(\textit{mx}\) 分别表示数组中的最小值和最大值。

如果数组中的所有元素都不相同，且数组的长度等于最大值和最小值之间的差值加 \(1\)，那么数组就是连贯数组，返回 \(\textit{true}\)；否则返回 \(\textit{false}\)。

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

1
2
3
4
class Solution:
    def isConsecutive(self, nums: List[int]) -> bool:
        mi, mx = min(nums), max(nums)
        return len(set(nums)) == mx - mi + 1 == len(nums)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public boolean isConsecutive(int[] nums) {
        int mi = nums[0], mx = 0;
        Set<Integer> s = new HashSet<>();
        for (int x : nums) {
            if (!s.add(x)) {
                return false;
            }
            mi = Math.min(mi, x);
            mx = Math.max(mx, x);
        }
        return mx - mi + 1 == nums.length;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    bool isConsecutive(vector<int>& nums) {
        unordered_set<int> s;
        int mi = nums[0], mx = 0;
        for (int x : nums) {
            if (s.contains(x)) {
                return false;
            }
            s.insert(x);
            mi = min(mi, x);
            mx = max(mx, x);
        }
        return mx - mi + 1 == nums.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func isConsecutive(nums []int) bool {
    s := map[int]bool{}
    mi, mx := nums[0], 0
    for _, x := range nums {
        if s[x] {
            return false
        }
        s[x] = true
        mi = min(mi, x)
        mx = max(mx, x)
    }
    return mx-mi+1 == len(nums)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function isConsecutive(nums: number[]): boolean {
    let [mi, mx] = [nums[0], 0];
    const s = new Set<number>();
    for (const x of nums) {
        if (s.has(x)) {
            return false;
        }
        s.add(x);
        mi = Math.min(mi, x);
        mx = Math.max(mx, x);
    }
    return mx - mi + 1 === nums.length;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isConsecutive = function (nums) {
    let [mi, mx] = [nums[0], 0];
    const s = new Set();
    for (const x of nums) {
        if (s.has(x)) {
            return false;
        }
        s.add(x);
        mi = Math.min(mi, x);
        mx = Math.max(mx, x);
    }
    return mx - mi + 1 === nums.length;
};

评论