跳转至

4048. 统计等间距出现整数数目 I

难度简单

题目描述

给你一个整数数组 nums。

如果一个整数 x 满足以下条件，则被称为 特别 的：

  • x 在 nums 中 恰好出现三次。
  • x 的 所有 三次出现，在 nums 中都是 等间隔 的。换句话说，如果 x 的所有出现位置的下标为 i1 < i2 < i3，那么 i2 - i1 = i3 - i2。

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

 

示例 1:

输入: nums = [1,8,1,5,1,5,8,5]

输出: 2

解释:

  • 1 是特别的，因为它恰好出现三次，且出现的等间隔下标为 0、2 和 4。
  • 5 是特别的，因为它恰好出现三次，且出现的等间隔下标为 3、5 和 7。
  • 8 不是特别的，因为它只出现了两次。

因此，答案是 2。

示例 2:

输入: nums = [8,8,8,8]

输出: 0

解释:

8 不是特别的，因为它出现的次数不是恰好三次。因此，答案是 0。

示例 3:

输入: nums = [8,6,6,8,8]

输出: 0

解释:

8 出现的下标为 0、3 和 4，这些下标不是等间隔的。6 只出现了两次。因此，没有整数是特别的。

 

提示:

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

解法

方法一：哈希表

思考

\(n \le 100\)，即便对每个值再扫一遍数组也能通过。特别整数要求恰好出现三次，且三次下标成等差。

把同一值的下标收集到一起后，判断退化成两件事：列表长度是否为 \(3\)，以及首末下标之和是否等于中间下标的两倍。

用哈希表按值分组，一次遍历即可统计。

我们用哈希表记录每个整数出现的所有下标。遍历数组 \(\textit{nums}\)，将下标 \(i\) 加入 \(\textit{nums}[i]\) 对应的列表中。

然后遍历哈希表中的每个下标列表 \(\textit{pos}\)。若 \(\textit{pos}\) 的长度为 \(3\)，且 \(\textit{pos}[0] + \textit{pos}[2] = 2 \times \textit{pos}[1]\)（即三次出现等间隔），则该整数是特别的，将答案加 \(1\)。

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

1
2
3
4
5
6
7
8
class Solution:
    def countSpecialIntegers(self, nums: list[int]) -> int:
        g = defaultdict(list)
        for i, x in enumerate(nums):
            g[x].append(i)
        return sum(
            len(pos) == 3 and pos[0] + pos[2] == pos[1] * 2 for pos in g.values()
        )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int countSpecialIntegers(int[] nums) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            g.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }

        int ans = 0;
        for (List<Integer> pos : g.values()) {
            if (pos.size() == 3 && pos.get(0) + pos.get(2) == pos.get(1) * 2) {
                ans++;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countSpecialIntegers(vector<int>& nums) {
        unordered_map<int, vector<int>> g;
        for (int i = 0; i < nums.size(); i++) {
            g[nums[i]].push_back(i);
        }

        int ans = 0;
        for (auto& [x, pos] : g) {
            if (pos.size() == 3 && pos[0] + pos[2] == pos[1] * 2) {
                ans++;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func countSpecialIntegers(nums []int) int {
    g := make(map[int][]int)
    for i, x := range nums {
        g[x] = append(g[x], i)
    }

    ans := 0
    for _, pos := range g {
        if len(pos) == 3 && pos[0]+pos[2] == pos[1]*2 {
            ans++
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function countSpecialIntegers(nums: number[]): number {
    const g = new Map<number, number[]>();

    for (let i = 0; i < nums.length; i++) {
        if (!g.has(nums[i])) {
            g.set(nums[i], []);
        }
        g.get(nums[i])!.push(i);
    }

    let ans = 0;
    for (const pos of g.values()) {
        if (pos.length === 3 && pos[0] + pos[2] === pos[1] * 2) {
            ans++;
        }
    }
    return ans;
}

评论