3852. Smallest Pair With Different Frequencies

📘 題目敘述

給你一個整數陣列 nums，找出滿足 x < y 且兩者出現次數不同的最小字典序配對 [x, y]，若不存在回傳 [-1, -1]。

條件限制

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

🧠 解題思路

先排序，建立 times 紀錄每個值與次數。固定最小值作為 x，再往後找第一個頻率不同的值作為 y；因為已排序，這樣同時滿足最小 x、最小 y。

所有變數

• times：每個不同值與其頻率
• a：判斷數字是否出現過
• fst：固定的最小 x
• count：fst 的頻率

🪜 主要流程步驟

1. 排序 nums

確保不同值按遞增處理。

2. 建立頻率表 times

第一次出現就新增，重複出現就把次數加一。

3. 固定最小值為 x

取 times[0] 作為 x 與其頻率基準。

4. 找第一個頻率不同的 y

掃描 times，遇到頻率不同即回傳。

5. 否則回傳 [-1,-1]

代表所有數字頻率都相同。

⏱️ 複雜度

• 時間複雜度：O(n log n + n * u)
• 空間複雜度：O(u)

💻 程式碼實作

class Solution {
public:
    vector<int> minDistinctFreqPair(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<pair<int, int>> times;
        set<int> a;
        for (int i : nums) {
            if (!a.count(i)) {
                times.push_back({i, 1});
                a.insert(i);
            } else {
                for (int j = 0; j < times.size(); j++) {
                    if (times[j].first == i) {
                        times[j].second++;
                    }
                }
            }
        }
        int fst = times[0].first, count = times[0].second;
        for (auto& [x, y] : times) {
            if (y != count) {
                return {fst, x};
            }
        }
        return {-1, -1};
    }
};

🔗 題目連結

https://leetcode.com/problems/smallest-pair-with-different-frequencies/