4038. 统计特殊整数个数

题目描述

给你一个整数数组 nums。

如果整数 x 在 nums 中的所有出现位置都位于同一个连续区间内，则称 x 为 特殊整数。

返回 nums 中不同特殊整数的数量。

示例 1：

输入： nums = [1,2,2,1]

输出： 1

解释：

1 出现在下标 0 和 3，形成了两个分离的区间，因此它不是特殊整数。
2 在下标 [1, 2] 处形成一个连续区间，因此它是特殊整数。

因此，共有一个特殊整数。

示例 2：

输入： nums = [3,3,1,2,2,1]

输出： 2

解释：

3 在下标 [0, 1] 处形成一个连续区间，因此它是特殊整数。
1 出现在下标 2 和 5，形成了两个分离的区间，因此它不是特殊整数。
2 在下标 [3, 4] 处形成一个连续区间，因此它是特殊整数。

因此，共有两个特殊整数。

提示：

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

解法

方法一：统计每个整数所在的块数

把数组中每一段极大的连续相等元素称为一个块。整数 \(x\) 是特殊整数，当且仅当 \(x\) 恰好只构成一个块。

因此，我们遍历数组，当 \(i = 0\) 或 \(\textit{nums}[i] \neq \textit{nums}[i - 1]\) 时，说明位置 \(i\) 是一个新块的起点，我们将 \(\textit{cnt}[\textit{nums}[i]]\) 加一。遍历结束后，统计 \(\textit{cnt}\) 中值恰好为 \(1\) 的整数个数即为答案。

时间复杂度 \(O(n + M)\)，空间复杂度 \(O(M)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度，而 \(M = 100\) 是数组中元素的最大值。

Python3JavaC++GoTypeScript

class Solution:
    def countSpecialIntegers(self, nums: List[int]) -> int:
        cnt = Counter(x for i, x in enumerate(nums) if i == 0 or x != nums[i - 1])
        return sum(v == 1 for v in cnt.values())

class Solution {
    public int countSpecialIntegers(int[] nums) {
        int[] cnt = new int[101];
        for (int i = 0; i < nums.length; ++i) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                ++cnt[nums[i]];
            }
        }
        int ans = 0;
        for (int c : cnt) {
            if (c == 1) {
                ++ans;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int countSpecialIntegers(vector<int>& nums) {
        int cnt[101]{};
        for (int i = 0; i < nums.size(); ++i) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                ++cnt[nums[i]];
            }
        }
        return count(begin(cnt), end(cnt), 1);
    }
};

func countSpecialIntegers(nums []int) int {
    cnt := [101]int{}
    for i, x := range nums {
        if i == 0 || x != nums[i-1] {
            cnt[x]++
        }
    }
    ans := 0
    for _, c := range cnt {
        if c == 1 {
            ans++
        }
    }
    return ans
}

function countSpecialIntegers(nums: number[]): number {
    const cnt: number[] = Array(101).fill(0);
    for (let i = 0; i < nums.length; ++i) {
        if (i === 0 || nums[i] !== nums[i - 1]) {
            ++cnt[nums[i]];
        }
    }
    return cnt.filter(c => c === 1).length;
}

4038. 统计特殊整数个数

题目描述

解法

方法一：统计每个整数所在的块数

评论