1207. Unique Number of Occurrences

📘 題目敘述

給定一個整數陣列 arr，請判斷每個不同整數在陣列中出現的次數是否都「互不相同」。

• 若所有不同整數的出現次數都不重複，回傳 true
• 否則回傳 false

條件限制

• 1 <= arr.length <= 1000
• -1000 <= arr[i] <= 1000

🧠 解題思路

我的做法分成兩段：

1. 先排序 arr，把相同數字集中在一起
   • 這樣我就可以用一次掃描，把每個數字的出現次數算出來
   • 並把每個數字的「出現次數」存到 occ 裡
2. 再檢查 occ 裡的次數是否有重複
   • 我把 occ 再排序一次
   • 如果排序後有相鄰的兩個值一樣，代表有重複次數 → 回傳 false
   • 否則全部都不同 → 回傳 true

這樣的好處是：

我完全不用 hash table，也能靠排序 + 線性掃描完成「計數」與「去重檢查」。

所有變數

• occ：存每個不同數字的出現次數（例如某個值出現 3 次，就 push 3）
• now：
  • 第一段：記錄目前正在統計的數字值（用來判斷是否換數字）
  • 第二段：記錄 occ 排序後上一個出現次數（用來檢查是否重複）
• count：目前這個數字累積出現了幾次

🪜 主要流程步驟

第一步：排序 arr

• sort(arr.begin(), arr.end());
• 讓相同數字排在一起，方便直接統計連續段長度

第二步：掃描排序後的 arr，把每個數字的出現次數存進 occ

我用 now + count 來做「分段統計」：

情況一：遇到新數字（now != i）

• 代表前一個數字的統計結束
• 把前一段的 count 放進 occ
• 然後開始統計新數字：count = 1，now = i

情況二：還是同一個數字（now == i）

• 代表還在同一段裡
• count++ 繼續累加出現次數

最後因為 for 迴圈結束時，最後一段還沒被 push，所以我用：

• if (count) occ.push_back(count);

把最後一段補進去。

第三步：排序 occ，檢查出現次數是否重複

• 先 sort(occ.begin(), occ.end());
• 然後掃描 occ，檢查是否出現相鄰重複：

如果 now == j

• 代表這個次數和上一個次數一樣（重複）
• 直接回傳 false

否則

• 更新 now = j，繼續檢查下一個

全部掃完都沒重複，就回傳 true。

💡 為什麼「排序 occ 後看相鄰」就夠了？

• 若某個次數重複，例如 2 出現兩次
• 排序後它們一定會排在一起
• 所以只要檢查相鄰元素是否相同，就能抓到重複次數

💻 程式碼實作

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        vector<int> occ;
        int now = 10000, count = 0;
        sort(arr.begin(), arr.end());
        for (int i : arr) {
            if (now != i) {
                occ.push_back(count);
                count = 1;
                now = i;
            } else {
                count++;
            }
        }
        if (count) {
            occ.push_back(count);
        }
        sort(occ.begin(), occ.end());
        now = 10000;
        for (int j : occ) {
            if (now == j) {
                return false;
            }
            now = j;
        }
        return true;
    }
};

🔗 題目連結

https://leetcode.com/problems/unique-number-of-occurrences/