1426. Counting Elements

 1426. Counting Elements ( https://leetcode.com/problems/counting-elements )

It's a premium problem, I'm not a suscriber....

Description

Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr. If there are duplicates in arr, count them separately.

Example 1:
Input: arr = [1,2,3]

Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:
Input: arr = [1,1,3,3,5,5,7,7]

Output: 0
Explanation: No numbers are counted, cause there is no 2, 4, 6, or 8 in arr.

Constraints:
1 <= arr.length <= 1000
0 <= arr[i] <= 1000

因為題目說，最大的數就是 1000 個

最直覺的解法就是，用 0~1001 的 int 陣列，去紀錄出現過的數字次數

有三個 1，就把 cnt[2] += 1 三次

最後把 cnt 的值加總就是答案了

class Solution {
public:
    int countElements(vector<int>& arr) {
        int cnt[1001]{};
        for (int x : arr) {
            ++cnt[x];
        }
        int ans = 0;
        for (int x = 0; x < 1000; ++x) {
            if (cnt[x + 1]) {
                ans += cnt[x];
            }
        }
        return ans;
    }
};

可以看以下影片，最後有個動態的解題法

只要排序加一次 for 迴圈

邊走邊計算符合條件的次數

參考
https://www.youtube.com/watch?v=HCFlfV1JJUw&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=7

https://github.com/doocs/leetcode/blob/main//solution/1400-1499/1426.Counting%20Elements/README_EN.md