📘 題目敘述
給你一個整數陣列 nums。
考慮所有由 nums 中不同值 x 和
y 組成的配對，並且滿足：
x < y-
x和y在nums中出現的次數不同
在所有符合條件的配對中，先選擇
x 盡可能小的那一組；如果有多組配對的
x 相同，則選擇 y 盡可能小的那一組。
請回傳整數陣列 [x, y]。如果不存在符合條件的配對，回傳
[-1, -1]。
條件限制
1 <= nums.length <= 1001 <= nums[i] <= 100
🧠 解題思路
我這份寫法的想法是先把每個不同數字的出現次數算出來，存成
times 這個
vector<pair<int,int>>。
times[i].first是數字值times[i].second是它的出現次數
我先把 nums 排序，這樣我在建立
times 時遇到新數字會照小到大出現，最後
times 也會是照數字大小排序的。
建立頻率表後，我的目標是找最小的 x（所以直接拿
times[0] 當作
x），然後在後面找第一個頻率跟 x 不同的
y，因為
times 是照數值遞增，第一個找到的就是最小的
y。
如果整個掃完都沒有找到頻率不同的 y，就回傳
[-1,-1]。
所有變數
-
times：存每個不同數字與其出現次數(value, freq) -
a：用來判斷某個數字是否已經出現過（避免重複新增到 times） -
fst：目前選到的x（我用最小的那個數字） -
count：fst的出現次數，用來和其他數字頻率比較
🪜 主要流程步驟
1. 先排序 nums
我先把 nums 排序，確保接下來建立
times 時，數字會依照從小到大出現。
2. 建立 times：統計每個數字出現次數
我掃過排序後的
nums：若是第一次看到就新增，若已存在就找到對應項把次數加一。
3. 固定 x 為 times[0]，因為它的值最小
題目要最小的 x，而
times 是依照數字大小遞增，所以
times[0] 一定是最小值。
4. 從 times 後面找第一個頻率不同的 y
只要遇到某個數字的頻率和 count 不同，直接回傳
{fst, x}。
5. 找不到就回傳 [-1, -1]
如果全部數字的頻率都跟
fst 一樣，代表不存在符合條件的配對。
⏱️ 複雜度
- 時間複雜度：
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/contest/biweekly-contest-177/problems/smallest-pair-with-different-frequencies/